syntax analysis of expression!!

84 Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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.