Question

In the correct grammar above, what is the length of the derivation (number of steps starting from S) to generate the string $a^l{b}^m\text{with}l\ne m?$

• A. $l+m+2$
• B. $max(l,m)+3$
• C. $max(l,m)+2$
• D. $l+m+3$

Answer 1

The correct option is C $max(l,m)+2$

If grammar generates $a^n{b}^{0}or{a}^0{b}^n$ then the length is max (l, m) if it generates $a^l{b}^m$ initially we include two extra derivation so the total length is $max(l,m)+2.$