retagged by
284 views
0 votes
0 votes

The language generated by the following grammar is:

  • $S \rightarrow  aAb$
  • $A \rightarrow aAb / B$
  • $B \rightarrow  CC$
  • $C \rightarrow  bDa$
  • $D \rightarrow  bDa / \epsilon$
  1. $\{ {a^m \;b^n \;a^n\; b^p \;a^p\; b^m } \mid m,n,p > 0\;\}$
  2. $\{ {a^m \;b^n\; a^m\; b^n\; a^m\; b^n } \mid  m,n,p >0\; \}$
  3. $\{ { a^m\; b^n\; a^p\; b^p \;a^n\; b^m } \mid  m,n,p > 0 \;\}$
  4. $\{ { a^m\; b^m \;a^n\; b^n \;a^p\; b^p } \mid m,n,p > 0\; \}$
retagged by

1 Answer

0 votes
0 votes

Let's take some string:

$S\rightarrow aAb\rightarrow aaAbb\rightarrow aaBbb\rightarrow aaCCbb\rightarrow aabDaCbb\rightarrow aabDabDabb\rightarrow aabababb\rightarrow a^2b^1a^1b^1a^1b^2$

 

Option B and D eliminated.

 

$S\rightarrow aAb\rightarrow aBb\rightarrow aCCb\rightarrow abDaCb\rightarrow abDabDab\rightarrow abbDaabDab\rightarrow abbaabDab\rightarrow abbaabab\rightarrow a^1b^2a^2b^1a^1b^1$

 

Option C eliminated.


$Ans:A$

Answer:

Related questions

0 votes
0 votes
0 answers
2
Bikram asked Aug 12, 2017
256 views
Match the correct automation given in Y to its transition function in $X$:$\begin{array}{|l|l|} \hline {} & X & {} & Y \\ \hline I. & Q^* \Sigma \rightarrow Q & A. & \tex...
4 votes
4 votes
0 answers
3
Bikram asked Aug 12, 2017
602 views
The number of possible finite automata with two states $a0$ and $a1$ (where $a0$ is always the initial state over the alphabet $\{p, q\}$) which accepts empty language is...
0 votes
0 votes
1 answer
4
Bikram asked Aug 12, 2017
259 views
What is the regular expression corresponding to the above DFA?$(01 + (00)^*1)^*$$0^*10^*$$(10 + 0(00)^* (1 + 01) )^*$$0(00)^*10^*$