3.1 Con text-Free Grammars 91
(or, x 3 y, if G is understood), if there exists a sequence x = x0, xl, x2,... ,
Xn = y of sentential forms such that xi^3 xi+1 foralli=O,l,..., n-l.
In the above, if x 3 y, with x = S and y E C*, then we say the grammar
G generaates the sentence y, and say the sequence
is a derivation of the sentence y. The language L(G) generated by G is the
set of all strings over C that are generated by G; that is,
L(G) = {x E C* 1 S -r, x}.
G
A language is called a context-free language if it is generated by a context-free
grammar.
Example 3.1 Consider the context-free grummur Cl = ({S}, (0, 1}, {S + E,
S + OSl}, S). What is the language L(G1)?Solution. There is only one nonterminal symbol in G1 and the only rule that
retains that symbol is S + OSl. Thus, the only derivations of G1 are of the
form
s OS1 3 OOSll l l OnSln > Onln.
Thus, L(G1) = {Onln 1 n > - O}. cl
When we have more than one grammar rule with the same left-hand side,
such as
A--+x1, A-x2,.... A+xm,
we can combine them into one multiple rule:A + xl 1 x2 1 -0. I xm.
For instance, the rules in the above example G1 can be written as S + E I OSl.
Example 3.2 Consider the context-free grammar G2 = ({S, A, B}, {a, b}, R,
S), where R consists of the following rules:
S + ABA, A + a 1 bb, B -+ bS I E.What is the lunguuge L(G2)?SoEution. Since the nonterminal symbol A can only produce terminal symbols,
we may delay its substitution to the end. Therefore, the derivations of G2
have the following general form:
S + ABA 3 AbSA 3 AbABAA a AbAbSAA
3 A(bA)2BA3 + ... + A(bA)“BA”+l a A(bA)“A”+?