# GATE2017-1-37

4.7k 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
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
2

@neenavath sindhu

CFL is not closed under intersection means that intersection of 2 CFL's MAY or MAY NOT BE CFL. It does not necessarily means that intersection of 2 cfl can never be a cfl..

But when we say closed under something, like CFL is closed under union then we mean that UNION OF ALL CFL SHOULD BE CFL.

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
1
Isn't G1 and G2 both are context free language ? and CFL is not closed under intersection.
1

not closed means the result of intersection may or may not be CFL

$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.

edited
5
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 generates 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

## Related questions

1
5k views
Consider the following languages over the alphabet $\sum = \left \{ a, b, c \right \}$. Let $L_{1} = \left \{ a^{n}b^{n}c^{m}|m,n \geq 0 \right \}$ and $L_{2} = \left \{ a^{m}b^{n}c^{n}|m,n \geq 0 \right \}$. Which of the following are context-free languages? $L_{1} \cup L_{2}$ $L_{1} \cap L_{2}$ I only II only I and II Neither I nor II
If $G$ is a grammar with productions $S\rightarrow SaS\mid aSb\mid bSa\mid SS\mid\epsilon$ where $S$ is the start variable, then which one of the following strings is not generated by $G$? $abab$ $aaab$ $abbaa$ $babba$
Consider the following context-free grammar over the alphabet $\Sigma = \{a,b,c\}$ with $S$ as the start symbol:$S \rightarrow abScT \mid abcT$$T \rightarrow bT \mid b$ ... $\{\left ( ab \right )^{n}\left ( cb^{n} \right )^{m} \mid m,n \geq 1 \}$
Consider the following languages: $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$ ... Which of the above languages are context-free? I and IV only I and II only II and III only II and IV only