Consider the context-free grammars over the alphabet \(\left \{ a, b, c \right…
2017
Consider the context-free grammars over the alphabet \(\left \{ a, b, c \right \}\) given below. \(S\) and \(T\) are non-terminals.
\(G_{1}:S\rightarrow aSb \mid T, T \rightarrow cT \mid \epsilon\)
\(G_{2}:S\rightarrow bSa \mid T, T \rightarrow cT \mid \epsilon\)
The language \(L\left ( G_{1} \right )\cap L(G_{2})\) is
- A.
Finite
- B.
Not finite but regular
- C.
Context-Free but not regular
- D.
Recursive but not context-free
Attempted by 70 students.
Show answer & explanation
Correct answer: B
Key idea: find the languages generated by each grammar and intersect them.
G1 generates strings of the form a^n c^m b^n with n,m ≥ 0 (from S → aSb | T and T → cT | ε).
G2 generates strings of the form b^p c^q a^p with p,q ≥ 0 (from S → bSa | T and T → cT | ε).
Any string in the intersection must match both shapes. That forces the numbers of leading a's and leading b's to be zero, so n = p = 0.
Conclusion: The intersection is exactly the set of strings consisting only of c's, i.e. { c^k : k ≥ 0 }, which is infinite and regular (equivalently described by the regular expression c*).
A video solution is available for this question — log in and enroll to watch it.