Mathematical Foundation of Computer Science

DHARM

282 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

l Starting state (q 0 ) will corresponds to the starting symbol S, and

l Set of productions (P) takes the meaning from the transition function (δ).

For example,

n If δ(A, a) = B is one of the transition function then its state diagram will be shown

in Fig. 11.3, i.e.,

A B

a

Fig. 11.3

from state A, automata consumes symbol a and reach to state B. Hence, the production will
A → aB, means that from non terminal symbol A, generate the variable symbol a and reach to
another non terminal symbol B.
n If δ(A, a) = B and state B is the final state then, state diagram will be as in
Fig.11.4 the productions are A → a, because automata terminates as soon as it
reaches to state B and A → a B, because machine reaches to state B after consuming
symbol a from state A.

A B

a

Fig. 11.4

n If starting state is the final state or δ(S, ε) = S then, state diagram will be as

Fig. 11.5

S

Fig. 11.5
Hence, S → ε will be the production.
Since, all above constructed productions must obey the restrictions 1, 2, 3 and 4. There-
fore, grammar is a Type-3 grammar.

Example 11.4. Let Σ = {a} and the language L = {ε} ∪ {a, aaa, aaaaa,......}. Since L is regular
hence there exists a DFA M shown in Fig. 11.6 that accepts the language L.

A B

a

S

a a

Fig. 11.6. (M)

Following transition functions can be translated into productions as follows,

l δ(S, a) = A ⇒ S → a A(S generates a and reaches to A)

l δ(A, a) = B ⇒ A → a B(A generates a and reaches to B)

l δ(B, a) = A ⇒ B → a A(B generates a and reaches to A)