S ABb|a|b A aaA|B B bAb Definition 6.5 conaa d c ea where a andre r. If we compa
ID: 3880194 • Letter: S
Question
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.Explanation / Answer
S ABb|a|b
A aaA|B
B bAb
For GNF all production are of form A->ax where x v*
Step1 : Replace B in A with B production ,
S ABb|a|b
A aaA|bAb
B bAb
Step2 : Replace A with A production in S ,
S aaABb|BBb|a|b
A aaA|bAb
B bAb
Step 3: Repace B in S with B production,
S aaABb|bAbBb|a|b
A aaA|bAb
B bAb
Therefore the given grammer in Greibach normal form is ,
S aaABb|bAbBb|a|b
A aaA|bAb
B bAb
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.