The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+28 votes
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
in Theory of Computation by Veteran (416k points)
edited by | 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.

8 Answers

+42 votes
Best answer

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

+14 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.
by Loyal (6.7k points)
+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.
by Junior (617 points)
edited by
+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.
+10 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 generates Language with Regular Expression

$R.E.= c^*$. 

That is not Finite but Regular. 

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

R.E.= c*. 

That is not Finite but Regular. 

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

by Active (1.4k points)
–4 votes
Option B
by Active (2.8k points)
0
Explain ur answers .....
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,839 questions
54,799 answers
189,488 comments
80,674 users