QUESTION

  1. Eliminate the variable B from the grammar

S → aSB|bB

B → aA|b

  1. Show that the two grammars

S → abAB|ba,

A → aaa,

B → aA|bb

and

S → abAaA|abAbb|ba,

A → aaa

are equivalent.

  1. In Example 6.1 Show a derivation tree for the string ababbac, using both the original and the modified grammar.

Example 6.1

Consider G = ({A, B}, {a, b, c}, A, P) with productions

A → a|aaA|abBc,

B → abbA|b

Using the suggested substitution for the variable B, we get the grammar Ğ

with productions

A → a|aaA|ababbAc|abbc,

B → abbA|b

The new grammar Ğ is equivalent to G. The string aaabbc has the derivation

A aaA aaabBc aaabbc

in G, and the corresponding derivation

A aaA ⇒ aaabbc

in Ğ.

Notice that, in this case the variable B and its associated production are still in the grammar even though they can no longer play a part in any derivation. We will next show such unnecessary productions can be removed from a grammar.

6. Eliminate all useless productions from the grammar.

S → aS|AB|λ,

A → bA,

B → AA.

What language does this grammar generate?

7. Eliminate all useless productions from

S → a|aA|B|C,

A → aB| λ,

B → Aa,

C → cCd,

D → ddd|Cd

8. Eliminate all λ- productions from

S → aSSS

S → bb| λ.

9. Eliminate all λ- productions from

S → AaB|aaB,

A → λ,

B → bbA| λ.

Public Answer

U3ADLG The First Answerer