edited by
341 views

1 Answer

Best answer
2 votes
2 votes

The answer is 6.

Except for the S productions, $S \rightarrow SS | ab$, all other are useless since we cannot reach them. So we can simply ignore them.

Now, the string $ababab$ have two derivation trees, hence is ambiguous.

$S \rightarrow SS \rightarrow abS \rightarrow abSS \rightarrow ababS \rightarrow ababab$

$S \rightarrow SS \rightarrow Sab \rightarrow SSab \rightarrow Sabab \rightarrow ababab$

I have not shown the derivation trees. But these derivations will give you the idea.

In the first derivation, we expand the second $S$ to get $SS$, while in the second derivation, we expand first $S$ to get $SS$. From this idea, I think you will be able to come up with two different derivation trees for $ababab$.

Any string shorter than this won't work. Why?

These are the derivable strings with the length less than 6: $ab$, $abab$.

Both of these strings have only one derivation tree.

selected by

Related questions

0 votes
0 votes
1 answer
1
2 votes
2 votes
1 answer
2
1 votes
1 votes
1 answer
3