Theoretical Computer Science question: Please explain in details. Question is at the bottom. I think (not sure) for A aaA|B, we can Subsititute B in place. so A aaA|bAb. But please go in greater details. Thanks and will rate. See the defination below, follow that. Convert the following grammar into Greibach normal form.

S ABb|a|b

A aaA|B

B bAb

Definition 6.5 conaa d c ea where a andre r. If we compare this with Definition 5.4, we see that the form ax is common to both Greibach does not carry the restriction that the pair (A. a) occur at most once. This additional freedom gives Greibach normal form a generality not normal form and s-grammars, but Greibach normal form possessed by s-gramars is not in Greibach ormal form, we may be able to rewrn i n s form with some If a orm, we may be able to rewrite it in of the techniques encountered above. Here are two simple examples. Example 6.9 The gramar S AB is not in Greibach normal form However, using the substitution given by Theorem 6.1, we immediately get the equivalent grammar which is in Greibach normal form