Mathematical Foundation of Computer Science

DHARM

302 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

(+) S → a X Y [S → a X Y Z when Z → ∈ is removed]

also production

(+) Z → a [Z → a A when A → ∈] but this is a repeatatine production so

there is no need to add further into the grammar.

Hence the new grammar G’ has following productions

S → a X Y Z | a b | a Y Z | a X Z | a X Y

X → a A b | A | a | a b

Y → b B a | B | b | b a

Z → a | a A | X Y

A → a | a A

B → b | b B

Example 11.20. A language L is expressed by the regular expression r = (a + b )*. b. b

. (a. b).
Express the grammar G i.e. L = L (G) and simplify it.
Sol. Let Grammar G can be defined as
G = (VN, {a, b}, S, P)
where, VN = {S and some other symbols} and set of productions P contains:
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 → ∈ [Y also generates string ε]
l Y → a b Y [Y derives the strings containing multiple of ‘ab’]
Thus, grammar G consists of above set of rules. Now, for simplification remove all null
productions from G. So, find the nullable symbols first, there are,
l X [because X ⇒ ∈], and
l Y [because Y ⇒ ∈].
hence [X, Y] are nullables.
So, after removing the nullable, from G we must add following productions,
(+) 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]
(+) Y → a b [from Y → a b Y when Y → ∈ is removed]
(+) Z → b [from Z → b Y when Y → ∈ is removed]
Hence we obtain the new grammar G′ i.e.,
S → W Z
W → X b | b
Z → b Y | b
X → a X | b X | a | b
Y → a b Y | a b
and its language s.t. L(G′) = L(G) – {∈}.