Let $L_{1}$ and $L_{2}$ be 2 languages over the same alphabet $\Sigma$.

$$A(L_1,L_2)=\{x\in \Sigma^*|\exists y,z\in L_2\text{ such that } yxz\in L_1\}$$

Assume that $L_{1}$ is regular and $L_{2}$ is context-free. The language $A(L_{1},L_{2})$:

  1. is always a regular language
  2. is always not a regular language
  3. can sometimes be a regular language
  4. cannot be context free

They say that the correct answer is 1.

  • 3
    $\begingroup$ check cs.stackexchange.com/questions/1547/… $\endgroup$
    – Ran G.
    Feb 28, 2013 at 2:50
  • $\begingroup$ Wow, thanks ! I'm shocked to see the answer to that question. $\endgroup$
    – Robert777
    Feb 28, 2013 at 6:45
  • $\begingroup$ @Robert777 So this is a duplicate? $\endgroup$
    – Raphael
    Feb 28, 2013 at 10:10
  • $\begingroup$ @Raphael Pretty much. $\endgroup$ Mar 1, 2013 at 3:37

1 Answer 1


Hint: Take a DFA for $L_1$. Check which states are reachable from the initial state via a word in $L_2$. Check from which states a final state can be reached via a word in $L_2$.


Not the answer you're looking for? Browse other questions tagged or ask your own question.