retagged by
8,418 views
39 votes
39 votes

$A$ CFG $G$ is given with the following productions where $S$ is the start symbol, $A$ is a non-terminal and a and b are terminals.

  • $S → aS \mid A$
  • $A → aAb \mid bAa \mid \epsilon$

For the string "$aabbaab$" how many steps are required to derive the string and how many parse trees are there?

  1. $6$ and $1$
  2. $6$ and $2$
  3. $7$ and $2$
  4. $4$ and $2$
retagged by

1 Answer

Best answer
53 votes
53 votes
$S\underset{1}{ \rightarrow} aS$
$\quad \underset{2}{\rightarrow} aA$
$ \quad \underset{3}{\rightarrow} aaAb$
$\quad \underset{4}{ \rightarrow} aabAab$
$\quad \underset{5}{ \rightarrow} aabbAaab$
$\quad \underset{6}{ \rightarrow} aabbaab$

Thus $6$ steps are needed and only one way to derive the string so only one parse tree.

Correct Answer: $A$
edited by
Answer:

Related questions

39 votes
39 votes
4 answers
1
3 votes
3 votes
4 answers
2
Harit asked Apr 25, 2016
5,402 views
Consider the following grammar. How many back tracks are required to generate the string aab from the above grammar?S → aB | aAbA → bAb | aB → aB | ε
54 votes
54 votes
8 answers
4
Ishrat Jahan asked Oct 29, 2014
11,779 views
Host $X$ has IP address $192.168.1.97$ and is connected through two routers $R1$ and $R2$ to an­other host $Y$ with IP address $192.168.1.80$. Router $R1$ has IP address...