Problem Solving in Automata, Languages, and Complexity

90 CONTEXT-FREE LANGUAGES

(2.1) We select a nonterminal symbol (a> in the sentential form and
replace it by the right-hand side of a grammar rule whose left-
hand side is (a>.
For instance, we can use the above grammar rules to generate the sentence
water evaporates constantly as follows:

(sentence) (subject) (predicate)

+ (noun) (predicate)

3 (noun) (verb) (adverb)

water (verb) (adverb)

water vaporat es (adverb)

water vaporat es constantly

The above grammar rules have the simple form

where A is a nonterminal symbol and x is a string of nonterminal and terminal

symbols. Grammar rules of this form can be used to generate a rich class of

Engliah sentences. We call a grammar with rules of this form a context-free

grammar.

We remark that a grammar for a natural language contains both syntuctic

rules, which describe the structure of a sentence, and semantic rules, which

describe the meanings of the words in a sentence. Context-free grammars are

only an approximation to the syntactic rules of the natural language gram-

mars, and do not deal with semantics in most cases.

Formally, we define a context-free grammar to be a quadruple (V, C, R, S)

of the following four components:

V: a finite set of nonterminal symbols;

C: a finite set of terminal symbols;

R: a finite set of rules which are of the form A + x, where A E V and

x E (v u c)*;

S: a special symbol in V, called the starting symbol.

Let G = (V, C, R, S) b e a context-free grammar. Then, we call a string

x E (VuC)* a sentential form, and a string y E C* a sentence. Let U, v be

two strings in (V U C)* and A E V. Then, we write

UAW 2 uxv

(or, UAW 3 uxv, if G is understood), if (A -+ x) is a rule in R. That is, we

can substitute string x for symbol A in a sentential form if (A + x) is a rule

in R. For any two sentential forms x and y, we write