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

The Gateway to Computer Science Excellence

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

+48 votes

Best answer

+16 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.

+11 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.

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,229 answers

197,977 comments

104,565 users