• edited by
578 views

1 Answer

Best answer
2 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
Position:
Show:

Related questions

0 0 votes
1 1 answer
521
521 views
2 2 votes
1 1 answer
1.5k
1.5k views
charul asked Jan 9, 2018
1,489 views
I'm getting 4, can someone verify
1 1 vote
1 answers 1 answer
1.3k
1.3k views
Vineeta Garg asked Dec 10, 2016
1,314 views
How it is left factored??
1 1 vote
1 answers 1 answer
596
596 views