Consider L = L₁ ∩ L₂

Where L₁ = {0^m1^m20ⁿ1ⁿ |m, n >= 0}

L₂ = {0^m1ⁿ2^k | m, n, k ≥ 0}

Then, the language L is

The correct answer is option 3.

Key Points

• L1 will first contain 0's followed by an equal number of 1's. After that, there will be a single 2 which will again be followed by 0's and an equal number of 1's i.e.   L1={2,012,00112,20011,01201,0011201,0120011,001120011,........}
• L2={epsilon,0,1,2,01,12,012,00112,20011,01201,0011201,0120011,001120011,............}
• L=L1∩L2={2,012,00112,0001112,........}
• L=L1∩L2={0^m1^m2/ m>=0}, which is a context free language but not regular language.

∴ Hence the correct answer is Context-free but not regular.

Additional Information