Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 301

l Third iteration,
Old V = {B, A, S} and new V = {B, A, S} with non existence of other nullable.
Now, old V equal to new V so while loop is terminated and program is terminated.
Hence, nullable symbols are {B, A, S}.
Remove all nullables. Simultaneously we add following productions (so that meaning of
the grammar doesn’t change).
(+) S → B [derive from S → A B when A → ∈]
(+) S → A [derive from S → A B when B → ∈]
Thus we obtain grammar G′ i.e.,
S → a b | A B | A | A
S → a b | A B | A
A → B | a and B → S | b
and its language L (G′) = L(G) – {∈}. Alternatively we say that grammar G′ generates the
similar set of strings as grammar G except the null string (∈).
To generate string ε by G′ add the production Snew → ∈ | S, so the grammar G′ becomes
Snew → ∈ | S
S → a b | A B | A
A → B | a
B → S | b
Example 11.19. A grammar G has the production
S → a X Y Z | a b
X → a A b | A | a
Y → b B a | B | b
Z → a | a A | X Y
A → ∈ | a | a A
B → ∈ | b | b B
Simplify the grammar (by removing all null productions).
Sol. Find nullable symbols that are
l B[∴ B ⇒∈]
l A[∴ A ⇒∈]
l Y[∴ Y ⇒ B ⇒∈]
l X[∴ X ⇒ A ⇒∈]
l Z[∴ Z ⇒ XY ⇒∈Y ⇒∈ ∈⇒∈]
So, {B, A, Y, X, Z} are nullables.
After dropping the nullables add following productions i.e.
(+) X → a b [X → a A b when A → ∈ is removed]
(+) Y → b a [Y → b B a when B → ∈ is removed]
(+) Z → X [Z → X Y when Y → ∈ is removed]
(+) Z → Y [Z → X Y when X → ∈ is removed]
(+) S → a Y Z [S → a X Y Z when X → ∈ is removed]
(+) S → a X Z [S → a X Y Z when Y → ∈ is removed]