3.3k 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.3k 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
+1

@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).

by Active (3.4k points)
edited
0
Isn't G1 and G2 both are context free language ? and CFL is not closed under intersection.
0

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.
by Loyal (6.7k points)
(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.
by Junior (617 points)
edited
+3
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.

by Active (3.7k points)
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.

by Active (3.7k points)
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
by Active (3.9k points)

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

by Active (1.4k points)
Option B
by Active (2.8k points)
0

1
2