# Operation on languages results in CFL

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?

• What do you think? What have you tried? Where did you get stuck? Aug 29 '17 at 9:10
• @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 Aug 29 '17 at 9:46
• I'm not sure why the counterexample is relevant - here we are interested in a different operation. Aug 29 '17 at 9:52
• As it happens, the answer to 1 is "false" and to 2 is "true". Aug 29 '17 at 9:58
• 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. Aug 29 '17 at 10:00