search
Log In
35 votes
4.7k 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
edited by
4.7k 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
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.

8 Answers

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


edited by
1
Isn't G1 and G2 both are context free language ? and CFL is not closed under intersection.
1

not closed means the result of intersection may or may not be CFL

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

edited by
5
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.
12 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. 


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. 

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

–4 votes
Option B
0
Explain ur answers .....
Answer:

Related questions

30 votes
6 answers
1
5k views
Consider the following languages over the alphabet $\sum = \left \{ a, b, c \right \}$. Let $L_{1} = \left \{ a^{n}b^{n}c^{m}|m,n \geq 0 \right \}$ and $L_{2} = \left \{ a^{m}b^{n}c^{n}|m,n \geq 0 \right \}$. Which of the following are context-free languages? $L_{1} \cup L_{2}$ $L_{1} \cap L_{2}$ I only II only I and II Neither I nor II
asked Feb 14, 2017 in Theory of Computation Arjun 5k views
30 votes
6 answers
2
3.4k views
If $G$ is a grammar with productions $S\rightarrow SaS\mid aSb\mid bSa\mid SS\mid\epsilon$ where $S$ is the start variable, then which one of the following strings is not generated by $G$? $abab$ $aaab$ $abbaa$ $babba$
asked Feb 14, 2017 in Theory of Computation Arjun 3.4k views
50 votes
5 answers
3
6.8k views
Consider the following context-free grammar over the alphabet $\Sigma = \{a,b,c\}$ with $S$ as the start symbol:$S \rightarrow abScT \mid abcT$$T \rightarrow bT \mid b$ ... $\{\left ( ab \right )^{n}\left ( cb^{n} \right )^{m} \mid m,n \geq 1 \}$
asked Feb 14, 2017 in Theory of Computation Arjun 6.8k views
31 votes
10 answers
4
6.8k views
Consider the following languages: $\{a^mb^nc^pd^q \mid m+p=n+q, \text{ where } m, n, p, q \geq 0 \}$ $\{a^mb^nc^pd^q \mid m=n \text{ and }p=q, \text{ where } m, n, p, q \geq 0 \}$ ... Which of the above languages are context-free? I and IV only I and II only II and III only II and IV only
asked Feb 14, 2018 in Theory of Computation gatecse 6.8k views
...