edited by
7,901 views
34 votes
34 votes

In the context-free grammar below, $S$ is the start symbol, $a$ and $b$ are terminals, and $\epsilon$ denotes the empty string.

  • $S \to aSAb \mid \epsilon$
  • $A \to bA \mid \epsilon$

The grammar generates the language

  1. $((a + b)^* b)$
  2. $\{a^mb^n \mid m \leq n\}$
  3. $\{a^mb^n \mid m = n)$
  4. $a^* b^*$
edited by

5 Answers

Best answer
72 votes
72 votes

$A \to bA \mid \varepsilon$

$\therefore \quad A = b^*$


$S \to aSAb \mid \varepsilon$

$\equiv S \to aSb^*b \mid \varepsilon$

$\equiv S \to aSb^+ \mid \varepsilon$


$S = a^n\left(b^+\right)^n, \quad n\geq 0$

$S = a^nb^nb^*, \quad n\geq 0$

$S = a^mb^n, \quad m\leq n$

Hence, option B is correct.

edited by
8 votes
8 votes

1) Epsilon is in grammar but can`t generate from this expression.
2) Can generate the exact language from this expression refer above answer.
3) abb is one of the string that can be generate from the given grammar but not by regular exp CONTRADICTION
4) aaaabb is the string that can be generated by this regular expression but not by grammar.

1 votes
1 votes
Option B is also wrong because option B says that we can generate any number of B, but they should be greater than equal to number of A. OPTION B can generate bbb, but  given CFG doesn't.
1 votes
1 votes

B is correct.

  1.  Incorrect as ((a+b)*b) can generate strings like aaaab which is not possible with given grammar.
  2.  Correct.
  3.  Also incorrect not always we will have a’s and b’s of same length, hence false
  4. a*b* can generate strings where a’s is greater than b false again.
Answer:

Related questions

45 votes
45 votes
4 answers
4