-
Consider the context-free grammars over the alphabet {a, b, c} given below. S and T are non-terminals.
G1 : S → aSb / T, T → CT | ∈
G2 : S → bSa \ T, T → cT | ∈
The language L(G1) ∩ L(G2) is
-
- Finite.
- Not finite but regular.
- Context-Free but not regular.
- Recursive but not context-free.
- Finite.
Correct Option: B
The context free grammar given over alphabets
∑ = {a, b, c}, with S and T are nonterminals.
Given, G1 : S → aSb | T , T → cT | ∈
G2 : S → bSa | T , T → cT | ∈
Lets L(G1) is the language for Grammar (G1) and L(G2) is the language for Grammar (G2).
where L(G1) = { an cm bn | m , n ≥ 0 }
L(G2) = { bn cm an | m , n ≥ 0 }
then L(G1) ∩ L(G2) = { an cm bn } ∩ { bn cm an }
= { cm | m ≥ 0 } = C*
Since the only common strings will be those strings with only ‘C’, so the intersection is not finite but regular.