Problem Solving in Automata, Languages, and Complexity

3.1 Context-Free Grammars 95

1 w

Figure 3.1: DFA for Example 3.8.

(a)

Figure 3.2: Two NFA’s for Example 3.9.

+J~@

01 &

Y

D

010

09

Example 3.8 Construct a context-free grammar that generates the regular

language accepted by the DFA in Figure 3.1.

Solution. From the proof of Theorem 3.7, we define a grammar G =

(V,C, R,S), with V = {S, A, B, C}, C = (0, l}, and the following rules:

5' + OA 1 lB, A --+ OA 1 lC, B + OC 1 lB, C + oc 1 ic I IZ. q

The method of Theorem 3.7 can also be applied to construct a context-free

grammar directly from an NFA.

Example 3.9 Construct a context-free grammar that generates the regular

language accepted by the NFA in Figure 3.2(a).

Solution. From the transition diagram of Figure 3.2(a), we can define the

grammar G1 = (V, (0, l}, R,S), with V = {S, A, B, C, 13, E, F} and rules

S + OA I OC, A + OB, B --+ E,

C + lD, D + 0-E I B, E + lF,

F + OD.