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

35 votes

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

- Finite
- Not finite but regular
- Context-Free but not regular
- Recursive but not context-free

0

** regular **language is a CFL. so how come it is regular language?? Anyone please explain this

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

53 votes

Best answer

17 votes

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

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

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

12 votes

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

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.

12 votes

**Answer: Option (B)**

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

*Here there is common production *

T -> cT |

**What that represents! That generates Language with Regular Expression **

6 votes

**Answer: Option (B)**

*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**

5 votes

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

hence finite

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

it is not finite but regular

corret ans is B

5 votes

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**