Question

Consider the context-free grammers over the alphabet { a, b, c } given below. S and T are non- terminals.
$G_1:S\to aSb\mid T,T\to cT\mid ϵ$
$G_2:S\to bSa\mid T,T\to cT\mid ϵ$
$ThelanguageL\left(G_1\right)\cap L\left(G_2\right)is$

• A. Recursive but not context-free
• B. Finite
• C. Not finite but regular
• D. Context-free but not regular

Answer 1

The correct option is C Not finite but regular

$G_1:S\to aSb\mid T,T\to cT\mid ϵ$

$G_2:S\to bSa\mid T,T\to cT\mid ϵ$

$L\left(G_1\right)=\{a^n{c}^m{b}^n\mid m,n\ge 0\}$

$L\left(G_2\right)=\{b^n{c}^m{a}^n\mid m,n\ge 0\}$

$L\left(G_1\right)\cap L\left(G_2\right)=\left\{a^n{c}^m{b}^n\right\}\cap \left\{b^n{c}^m{a}^n\right\}$

= $\{c^m\mid m\ge 0\}$

= $c^{\ast }$

Since the only common strings will be those strings with only 'c' , since in the first language all the other strings start with 'a' and in the second language all the other strings start with 'b'.

Clearly the intersection is not finite but regular.