Problem Solving in Automata, Languages, and Complexity

3

Context-Free Languages

3.1 Context-Free Grammars

In the study of natural languages, a grammar is a set of rules that govern how
sentences in a language are generated. For instance, the English grammar
contains, among others, the following rules:

(sentence) + (subject) (predicate)

(subject) + (noun)

(predicate) + ( verb) (adverb)

(noun) + water

(verb)

(adverb)

evaporates

constantly

To explain how these grammar rules work, let us call terms of the form
( l. 0) nonterminal symbols and words in English terminal symbols. (Thus,
an English sentence, in the terminology of formal languages, is a string over
terminal symbols.) We call a string formed by nonterminal and terminal
symbols a sentential form, and call a string formed by terminal symbols only
a sentence. We can generate a sentence from the above given grammar rules
as follows:
(1) First, we create a sentential form of a single symbol (sentence).
(2) We repeatedly preform the substitution of (2.1) until the sentential form
contains only terminal symbols:
89

Problem Solving in Automata, Languages, and Complexity.

Ding-Zhu Du, Ker-I Ko

Copyright2001 by John Wiley & Sons, Inc.

ISBNs: 0-471-43960-6 (Hardback); 0-471-22464-2 (Electronic)