GATE CSE 2017 Set 1 | Question: 37

Question

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

• A. Finite
• B. Not finite but regular
• C. Context-Free but not regular
• D. Recursive but not context-free

Comments

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

---

The statement is too underrated given by @Hirak. Closed means compulsory while not closed means possibility.

---

G1, produce L1={a^nc^mb^n | n,m>=0}; so L1 is cfl=> Read ‘a’ push ‘a’ into stack, seen ‘c’ skip, read ‘b’, pop off ‘a’.   G2, produce L2={b^nc^ma^n | n,m>=0};  Read ‘b’ push ‘b’ into stack, seen ‘c’ skip, read ‘a’, pop off ‘b’.  Now, both are cfl but when you apply intersection operation then you got c  is common(m,n have no restriction ) it mean you got infinite length of language(c,cc,ccc, …), but c is finite length of strings, cunstruct dfa for c; if you construct dfa, you say that language is Regular. but language is infinite.

Answer 1

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

R.E.= c*. 

That is not Finite but Regular. 

Answer 2

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

Answer 3

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

Answer 4

Option B

Comments

Explain ur answers .....