0

I have a question. Given the following grammar: $$S \to ABC$$ $$A \to aA| \varnothing$$ $$B \to bB|a$$ $$C \to bCb|aCb|\varnothing$$

I found that its Chomsky form is: $$S \to AS'|BC|AB|VB|a$$ $$S' \to BC$$ $$A \to UA'|UU$$ $$A' \to AU$$ $$B \to VB|b$$ $$C \to VC'|UC'|VV|UV$$ $$C' \to CV$$ $$U \to a$$ $$V \to b$$}

I want to make a syntax analysis of the expression $aabaaabb$. But...how can I do this?

evinda
  • 7,823

1 Answers1

2

To derive aabaaabb, first note that all the expression produced with your second and third rule must end by a, so an expression ending with b is necessarily an otcome of rule S or C (and in the former case one of the operands or rule S is already a non-empty outcome of rule C).

In general, you can find the general expression for, say expressions of type "A", that are (possibly empty) sequences of a, of type "B", which are possibly empty sequences of b followed by exactly one a, and of type $C$, which are even sequences of letters where the second half are all b.

Your expression is not of type C so it's an S = ABC, where A is aa, B is ba and C is aabb.

Of course you have to prove that this is the only possible derivation, but this is quite simple.

rewritten
  • 3,092
  • 1
    Nice...Thank you very much!!! – evinda Jan 13 '14 at 18:42
  • 2
    As an example of expression with multiple possible derivation, take $babbbb$. It can be derived by three applications of C: $∅→_Cbb→_Cabbb→_Cbabbbb$, and by using $S=(∅)(ba)(bbbb)$ where $a→_Bba$ and $∅→_Cbb→_Cbbbb$. – rewritten Jan 13 '14 at 19:21