and
Continue this process, introducing V 2 and
and so on, until no terminals remain on the left. Then use a similar process
to remove terminals on the right.
9. This normal form can be reached easily from CNF. Productions of the form A
→ BC are permitted since a = λ is possible. For A → a, create new variables
V 1 , V 2 and productions A → aV 1 V 2 , V 1 → λ, V 2 → λ.
12. Solutions:
15. Only A → bABC is not in the required form, so we introduce A → bAV and
V → BC. The latter is not in correct form, but after substituting for B, we
have
Section 6.3
2. Since aab is a prefix of the string in Example 6.11, we can use the V ij
computed there. Since S ∈ V 13 , the string aab is in the language generated by
the grammar and can therefore be parsed.
For parsing, we determine the productions that were used in justifying S ∈
V 13 :
Continue this process, introducing V 2 and
and so on, until no terminals remain on the left. Then use a similar process
to remove terminals on the right.
9. This normal form can be reached easily from CNF. Productions of the form A
→ BC are permitted since a = λ is possible. For A → a, create new variables
V 1 , V 2 and productions A → aV 1 V 2 , V 1 → λ, V 2 → λ.
12. Solutions:
15. Only A → bABC is not in the required form, so we introduce A → bAV and
V → BC. The latter is not in correct form, but after substituting for B, we
have
Section 6.3
2. Since aab is a prefix of the string in Example 6.11, we can use the V ij
computed there. Since S ∈ V 13 , the string aab is in the language generated by
the grammar and can therefore be parsed.
For parsing, we determine the productions that were used in justifying S ∈
V 13 :