3.2k views

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

1. Finite
2. Not finite but regular
3. Context-Free but not regular
4. Recursive but not context-free
edited | 3.2k views
0

Here both G1 and G2 are CFL. So intersection of two CFLs are not closed.. therefore it is not a CFL but every regular language is a CFL. so how come it is regular language?? Anyone please explain this

0
Why not C?

L(G1)=a^nc^mb^n|n≥0

L(G2)=b^nc^ma^n|n≥0

L(G1)∩L(G2)=c^m

Since while intersection all strings produced by production $aSb$ in $G_1$ and $bSa$ in $G_2$ will be $0$

So, only common production will be:

$S \rightarrow T$

$T \rightarrow cT \mid \epsilon$

Which is nothing but $c^*$ hence it is REGULAR and INFINITE

So, option is (B).

edited
0
Isn't G1 and G2 both are context free language ? and CFL is not closed under intersection.
$L(G1)=a^{n}c^{*}b^{n} |n\geq 0$

$L(G2)=b^{n}c^{*}a^{n} |n\geq 0$

$L(G1)\cap L(G2)=c^{*}$ which is not finite but regular.
(B)

L1 is a^n b^n c^m

L2 is b^na^n c^m

The intersection is possible only when n = 0 in both the cases and m is equal. This gives a regular infinite language.
+2
Correct explanation :

L(G1)=a^nc^∗b^n | n≥0

L(G2)=b^nc^∗a^n | n≥0

L(G1)∩L(G2)=c^∗  which is infinite and regular.

We can also solve this Question by observing the productions given.

Here there is common production

G:   S -> T
T -> cT |
ϵ

What that represents ! That geneates Language with Regular Expression

## That is not Finite but Regular.

edited

We can also solve this Question by observing the productions given.

Here there is common production

G:   S -> T
T -> cT |
ϵ

What that represents ! That geneates Language with Regular Expression

## That is not Finite but Regular.

g1 intersection g2 = phi , here so it is regular

hence finite

but here t-> ct /epsilon which is comman in both so

it is not finite but regular

corret ans is B

no need to to think much straight forward question is given

G1: starting with a and ending with b (compulsory conditon) or contains infinite c

G2: starting with b and ending with  a (compulsory condition) or contains infinite c

so both are intersection will give 0 strings because if string is starting from 'a' than how it can start form b

and second half part where c is infinite and regular so option B

Option B
0

1
2