DHARMNON-REGULAR GRAMMARS 303
Example 11.21. Similar to previous example, let language L is expressed by the regular ex-
pression
r = (a + b ). b. b. (a + b)
Express its grammar and simplify it.
Sol. Assume grammar G = (VN, {a, b}, S, P) then it expresses the language s.t. L(G) = L (r),
where we can consult following let of productions, i.e.
l S → W Z [assume W is responsible for generating the strings for (a + b ). b
and Z is responsible for generating the strings for b. (a + b )]
l W → X b [symbol X generate the strings corresponds to (a + b )]
l Z → b Y [symbol Y generate the strings corresponds to (a + b)]
l X → ∈ [X also generates string ε]
l X → a X | b X [all strings formed over {a, b}either start with symbol a or b]
l Y → X [Y is similar to X]
So nullables are {X, Y}.
Now following productions are added in G after removing the nullables,
(+) X → a [from X → a X when X → ∈ is removed]
(+) X → b [from X → b X when X → ∈ is removed]
(+) W → b [from W → X b when X → ∈ is removed]
(+) Z → b [from Z → b Y when Y → ∈ is removed]
(Y → X remains there in grammar for holding rest of the definition of X excluding
deriving ∈)
Thus we obtain a new grammar G′ i.e.,
S → W Z
W → X b | b
Z → b Y | b
X → a X | b X | a | b
Y → X
That has the language s.t. L(G′) = L(G) – {∈}.
- Remove all useless productions
A production is said to be useless if there is no way to reach to that production in the grammar.
So, a production α → β is useless if and only if the non terminal symbol α is non reachable from
any deriving non terminal in the grammar s.t. for all productions
γ → λ then λ ≠ α
Then α is the useless symbol of the grammar. A symbol is again useless if it is non
terminative, i.e. For example, A → a A | b A. In this production there is no way to come out
from the definition of A or there is no recovery derivation is defined from A. Since, A is non
terminative so A is a useless symbol and simultaneously this production is a useless production
for the grammar. So, during simplification of the grammar we remove all useless production/s
and also useless symbol/s. For example a grammar is expressed using following productions
S → A B | a
A → a A | b A
B → a | a B