and if we associate the actual words “a” and “the” with
“boy” and
“dog” with
, and “runs” and “walks” with
, then the grammar tells
us that the sentences “a boy runs” and “the dog walks” are properly formed. If
we were to give a complete grammar, then in theory, every proper sentence
could be explained this way.
This example illustrates the definition of a general concept in terms of simple
ones. We start with the top-level concept, here
, and successively
reduce it to the irreducible building blocks of the language. The generalization of
these ideas leads us to formal grammars.
Definition 1.1
A grammar G is defined as a quadruple
G =(V, T, S, P),
where V is a finite set of objects called variables,
T is a finite set of objects called terminal symbols,
S ∈ V is a special symbol called the start variable,
P is a finite set of productions.
It will be assumed without further mention that the sets V and T are nonempty
and disjoint.
The production rules are the heart of a grammar; they specify how the
grammar transforms one string into another, and through this they define a
language associated with the grammar. In our discussion we will assume that all
production rules are of the form
where x is an element of (V ∪ T) + and y is in (V ∪ T)*. The productions are
applied in the following manner: Given a string w of the form
we say the production x → y is applicable to this string, and we may use it to
replace x with y, thereby obtaining a new string
“boy” and
“dog” with
, and “runs” and “walks” with
, then the grammar tells
us that the sentences “a boy runs” and “the dog walks” are properly formed. If
we were to give a complete grammar, then in theory, every proper sentence
could be explained this way.
This example illustrates the definition of a general concept in terms of simple
ones. We start with the top-level concept, here
, and successively
reduce it to the irreducible building blocks of the language. The generalization of
these ideas leads us to formal grammars.
Definition 1.1
A grammar G is defined as a quadruple
G =(V, T, S, P),
where V is a finite set of objects called variables,
T is a finite set of objects called terminal symbols,
S ∈ V is a special symbol called the start variable,
P is a finite set of productions.
It will be assumed without further mention that the sets V and T are nonempty
and disjoint.
The production rules are the heart of a grammar; they specify how the
grammar transforms one string into another, and through this they define a
language associated with the grammar. In our discussion we will assume that all
production rules are of the form
where x is an element of (V ∪ T) + and y is in (V ∪ T)*. The productions are
applied in the following manner: Given a string w of the form
we say the production x → y is applicable to this string, and we may use it to
replace x with y, thereby obtaining a new string