-
Let L1 = L1 ∩ L2 , where L1 and L2 are languages as defined below
L1 = { am bm c an bn | m , n ≥ 0 }
L2 = { ai bj ck | i , j , k ≥ 0 }
Then L is
-
- not recursive
- regular
- context-free but not regular
- recursively enumerable but not context-free
- not recursive
Correct Option: C
It is given that L = L1 ∩ L2
Let' s first analyze the given language and check whether it is context-free or not. The context-free languages are defined as below -
A context-free language is L = { an bn : n ≥ 1 } that is the language of all non-empty even-length strings. It consists of
1. the entire first halves of which are a' s.
2. the entire second halves of which are b' s.
L is generated by the grammar S → aSb | ab, and is accepted by the push-down automata M = ({q0, q1, qf}, {a, b}, {a, z), δ q0, {qf}) where δ is defined as
δ(q0, a, z) = (q0, a)
δ(q0, a, a) = (q0, a)
δ(q0, b, a) = (q1, x)
δ(q1, b, a) = (q1, x)
δ(q1, λ, z) = (qf, z)
δ(state1, read pop) = (state2, push)
where z is initial stack symbol and x means pop action. Here, in we are given, where a and b are of equal lengths and followed by c which is of different length. This definitely shows that the languages are context-free but not regular.
