For every two languages $L_{1}$ and $L_{2}$ over the alphabet $\{ a,b,c,d \}$, we define the language $$L_{1} \operatorname{op} L_{2} = \{ \alpha\beta \mid \text{$\alpha \in L_{1}$ and $\beta \in L_{2}$ and $|\alpha| \le |\beta|$}\}.$$

1) If $L_{1}$ and $L_{2}$ are CFL then is $L_{1} \operatorname{op} L_{2}$ always CFL?

2) if $L_{1}$ and $L_{2}$ are regular languages then is $L_{1} \operatorname{op} L_{2}$ always CFL?

  • $\begingroup$ What do you think? What have you tried? Where did you get stuck? $\endgroup$ Aug 29 '17 at 9:10
  • $\begingroup$ @YuvalFilmus for 1) As a counterexample the intersection of 2 CFL is not CFL . 2) I think it is not true ,however I can't think of counterexample $\endgroup$
    – Johnas
    Aug 29 '17 at 9:46
  • $\begingroup$ I'm not sure why the counterexample is relevant - here we are interested in a different operation. $\endgroup$ Aug 29 '17 at 9:52
  • $\begingroup$ As it happens, the answer to 1 is "false" and to 2 is "true". $\endgroup$ Aug 29 '17 at 9:58
  • $\begingroup$ You are misunderstanding the question. You are given a specific operations, and the question asks what happens when you apply this operation to two context-free or regular languages. $\endgroup$ Aug 29 '17 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.