Redirected
edited by
8,467 views
14 votes
14 votes

Consider the context-free grammar $G$ below
\[
\begin{array}{l}
S \rightarrow a S b \mid X \\
X \rightarrow a X \mid X b \mid a \mid b,
\end{array}
\]
where $S$ and $X$ are non-terminals, and $a$ and $b$ are terminal symbols. The starting non-terminal is $S$.

Which one of the following statements is $\text{CORRECT}?$

  1. The language generated by $G$ is $(a+b)^{\ast}$
  2. The language generated by $G$ is $a^{\ast}(a+b) b^{\ast}$
  3. The language generated by $G$ is $a^{\ast} b^{\ast}(a+b)$
  4. The language generated by $G$ is not a regular language
edited by

5 Answers

5 votes
5 votes

Given productions of grammar G :

S → aSb / X  

X → aX / Xb / a / b 

 

NOTE : While finding the expression for any given Grammar G, always try to solve in bottom up fashion. 

 

For X : In X, any number of a & b can occur and when we wish to terminate, we have choice

between a & b.

 

So, X → $a^{m}(a+b) / (a+b)b^{p}$ $(m \geq 0, p \geq 0)$

 

Replace this X in above productions. Then productions will look like this :

S → aSb / $a^{m}(a+b) / (a+b)b^{p}$.

 


For S : Let’s first analyze S → aSb

S → aSb

S → aaSbb

S → aaaSbbb

  

This is simply, $a^{n}b^{n}$ ($n\geq 1$). Let’s Substitute this :

 

S → $a^{n}a^{m}(a+b)b^{n} / a^{n}(a+b)b^{p}b^{n}$

 

This can further be simplified as : $a^{*}(a+b)b^{*}$

Option B, is correct answer.

4 votes
4 votes
1 votes
1 votes

Detailed Video Solution: Context Free Grammar But Language Regular

$\color{\red}{\text{ALL Theory of Computation Questions & Detailed Solutions:}}$

Question 1: PDA Push Down Automata Question

Question 2: Number of States in the Minimal DFA

Question 3: Intersection Closure Property based Question

Question 4: DFA to Regular Expression question: 1(0+11)*

edited by
1 votes
1 votes
Answer to this question is B

If we see option a then it is wrong because we cannot produce string where a comes after b for example abbbaaaa and for same reason c is also wrong as it can produce single a after b so correct answer is b
Answer:

Related questions