Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 283

Since S and A are the final states hence, following are some more productions:

l Start state is the final state, means that machine M halts in real no consumption of

any input symbol. So, for transition function δ(S, ∈) = S ⇒ S ⇒ ∈ is a production.

l For those strings that are terminated on state A, the productions are,

S → a (stop) and B → a (stop)

Hence the set P contains following productions:

S → ∈/a/aA

A → aB

B → aA/a

Since, above productions obey the required restrictions (1, 2, 3 and 4) hence these pro-

ductions are from type-3 grammar.

We can also see that the language generated by grammar G is L(G) is same as the

language of DFA M or L(G) = L(M).

S ⇒∈ ≡ S ⇒ a,

S ⇒ a A ⇒ a a B ⇒ a a a,

S ⇒ a A ⇒ a a B ⇒ a a a A ⇒ a a a a B ⇒ a a a a a

So, L(G) = {∈, a, a a a, a a a a a, .........} = L(M)

Theorem 11.2. If L is generated from a Type-3 grammar G then L is regular.

Proof. Above theorem suggest the way how to construct the DFA from given grammar.

Let grammar G = (VN, VT, S, P) then the tuples of DFA M = (Q, Σ, δ, qo, F) relates the

tuples of G in following manner,

l Q = VN ∪ {qf} where qf is the new final state added in this set.

l Σ = VT

l q 0 = S

l F = {qf} ∪ {S} if ∈ ∈ L, or {qf} if ∈ ∉ L.

l From given definition of productions, transition functions are to be determin, i.e.

For example, ......

If productions of G are:

S → aA/a/∈ A → aB and B → a A/a

Then following will be the FA, (Fig. 11.7)

A B

a

S

a

a

qf

a

a

Fig. 11.7
Note that machine might be a NFA at this level. So convert it Fig. 11.7 to the DFA. i.e. the
minimum state DFA will be shown in Fig. 11.8.