Problem Solving in Automata, Languages, and Complexity

96 CONTEXT-FREE LANGUAGES

We note that the NFA can be simplified into a 3-vertex labeled digraph

with each edge labeled by a single string (see Figure 3.2(b)). From this labeled

digraph, we can actually get a simpler grammar G2 = ({S, B, D}, { 0, l}, R, S),

with the following rules in R:

s __) OOB 1 OlD, B --+&, D + OlOD 1 B. Cl

The grammar rules of Examples 3.8 and 3.9 all have the form

A+wB or A-w,

where A and B are nonterminal symbols and w is a string of terminal symbols.

If a context-free grammar consists of rules of these forms only, then we call

it a right-linear grammar. Symmetrically, we say a context-free grammar is a

left-linecar grammar if all its rules are of the form

A+Bw or A-w,

where A and B are nonterminal symbols and w is a string over terminal
symbols.

Theorem 3.10

lineur grammar

A language generated by a left-linear grammar or by a right-

must be a regular lunguuge.

Proof. Assume that G = (V, C, R, S) is a right-linear grammar. We define a
labeled digraph D as follows: The vertex set of D is V U {f}, where f 4 V.
Let S be the initial state and f the unique final state. For each rule in G of
the form A + wB, where A, B E V and w E C, draw an edge A w\ B (with
w as the label) in D. For each rule of the form A + w, where A E V and
w~C,drawanedgeA-%finD.
It is not hard to show that each derivation S 3 w of the grammar G
corresponds to a path in D from the initial vertex S to the final vertex f
whose label is w. Therefore, the language represented by this labeled digraph
D is exactly L(G). F rom the study of Chapters 1 and 2, we know that the
language represented by the labeled digraph D is regular (indeed, it can easily
be converted to an NFA) and, hence, L(G) is regular.
Next, assume that G1 = (V, C, RI, S) is a left-linear grammar. We con-
struct a right-linear grammar G2 = (V, C, R2, S), with

R2 = {A --+ wRB 1 (A + Bw) E RI} u {A + wR 1 (A + w) E RI}.

Now, for any derivation in G1

there is a corresponding derivation in G2: