edited by
12,048 views
48 votes
48 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

  1. Finite
  2. Not finite but regular
  3. Context-Free but not regular
  4. Recursive but not context-free
edited by

8 Answers

Best answer
75 votes
75 votes

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
26 votes
26 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.
13 votes
13 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
12 votes
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
Answer:

Related questions

44 votes
44 votes
6 answers
2
Arjun asked Feb 14, 2017
11,481 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 g...
74 votes
74 votes
8 answers
3