Problem Solving in Automata, Languages, and Complexity

3.1 Context-Free Grammars 97

Figure 3.3: Solution to Example 3.11.

Thus, it is clear that L(G2) = L(G#? From the first part of this proof, we

know that L(G 2 ) is regular. Thus, by Theorem 2.33, L(G1) is also regular. •I

From the above theorem, we say a context-free grammar is a regular grum-

mar if it is either right-linear or left-linear.

Example 3.11 Let G be a regular grammar with the following rules:

S --+ OlA 1 OOB 1 11, A -+ OB 1 1C loo,

B + OA ( lB, c __) 01s.

Construct an NFA accepting L(G).

Solution. From the construction in the proof of Theorem 3.10, we obtain a

labeled digraph as shown in Figure 3.3. It can be converted to an NFA easily.

0

Exercise 3.1

In the following exercises, each grammar is presented only with rules, with the
convention that all upper-case letters denote nonterminal symbols, all lower-
case letters and numerals denote terminal symbols, and S denotes the starting
symbol.

I. Describe, in English and/or by regular expressions, the language that is

generated by each of the following context-free grammars:

(a) S + uSa I bSb I a I b.

(b) S -+ aS I bS I E.

(c) S --+ aS 1 Sb I a.

(d) S ---+ SS I a I b.

(e) S -+ SS 1 aSb 1 E.

(f) s __) as I USbS I E.