retagged by
375 views
2 votes
2 votes
It is known that the language $L1 = \{0^n 1^n 2^i \mid i!= n\}$ is not a context free language(CFL).
Now consider the language
 $L2 = \{0^i 1^n 2^n \mid i != n\}$. We can prove $L2$ is not a CFL by converting $L2$ into $L1$ by applying two operations, both known to be closed on CFLs. What are the two operations you will use for this conversion?
Justify your answer.
retagged by

1 Answer

Best answer
6 votes
6 votes

To Convert L2 = {0^i 1^n 2^n | i != n} into L1 = {0^n 1^n 2^i | i != n} , We can apply two Operations

1. Reversal of L2 !! Thus, making L2 as { 2^n 1^n 0^i | i != n } 

and

2. Homomorphism as h(0) = 2 , h(1) = 1, h(2) = 0 , Thus, making L2 as  {0^n 1^n 2^i | i != n} which is same as L1.

And Set of all CFLs is closed under Reversal and Homomorphism.

selected by

Related questions

0 votes
0 votes
0 answers
1
baofbuiafbi asked Nov 14, 2023
151 views
Prove the language L={(G,H)|G is a CFG, H is a DFA, and L(G)∩L(H)=∅} is undecidable.