790
Modeling Arithmetic, Computation, and Languages
DefinitionS ContExt-sEnsitivE, ContExt-frEE, AnD rEGuLAr GrAMMArs;
ChoMsKy hiErArChy
A grammar G is context-sensitive (type 1) if it obeys the erasing convention and
if, for every production a S b (except S S l), the word b is at least as long as
the word a. A grammar G is context-free (type 2) if it obeys the erasing convention and for every production a S b, a is a single nonterminal. A grammar G
is regular (type 3) if it obeys the erasing convention and for every production
a S b (except S S l), a is a single nonterminal and b is of the form t or tW,
where t is a terminal symbol and W is a nonterminal symbol. This hierarchy of
grammars, from type 0 to type 3, is called the Chomsky hierarchy.
In a context-free grammar, a single nonterminal symbol on the left of a
production can be replaced wherever it appears by the right side of the production. In a context-sensitive grammar, a given nonterminal symbol can perhaps be replaced only if it is part of a particular string (context)—hence the
names context-free and context-sensitive. It is clear that any regular grammar
is also context-free, and any context-free grammar is also context-sensitive.
The grammar of Example 49 is regular (the two productions have the single
nonterminal S on the left, and on the right either 1—a terminal—or 0S—a terminal followed by a nonterminal). Both grammars of Example 51 are contextfree but not regular (again the single nonterminal S appears on the left of all
productions, but the right sides consist of three symbols or two nonterminals
or two terminals, respectively). The grammar of Example 52 is context-sensitive but not context-free (the productions do not shrink any strings, but some
left sides have multiple symbols). The grammars of Example 53 and Example
54 are context-free but not regular (for example, the first three productions of
Example 54 violate the requirement for a regular grammar). Finally, the grammar of Example 57 is a type 0 grammar, but it is not context-sensitive (for
example, the production EB S 0 is a “shrinking” production; also, the erasing
convention is violated).
Definition LAnGuAGE tyPEs
A language is type 0 (context-sensitive, context-free, or regular) if it can be
generated by a type 0 (context-sensitive, context-free, or regular) grammar.
Because of the relationships among the four grammar types, we can classify
languages as shown in Figure 9.26. Thus, any regular language is also context-free
because any regular grammar is also a context-free grammar, and so on. However,
although it turns out to be true, we do not know from what we have done that these
sets are properly contained in one another. For example, the language L described
in Example 57 was generated in that example by a grammar that was type 0 but
not context-sensitive, but that does not imply that L itself falls into that category.
Different grammars can generate the same language.
Modeling Arithmetic, Computation, and Languages
DefinitionS ContExt-sEnsitivE, ContExt-frEE, AnD rEGuLAr GrAMMArs;
ChoMsKy hiErArChy
A grammar G is context-sensitive (type 1) if it obeys the erasing convention and
if, for every production a S b (except S S l), the word b is at least as long as
the word a. A grammar G is context-free (type 2) if it obeys the erasing convention and for every production a S b, a is a single nonterminal. A grammar G
is regular (type 3) if it obeys the erasing convention and for every production
a S b (except S S l), a is a single nonterminal and b is of the form t or tW,
where t is a terminal symbol and W is a nonterminal symbol. This hierarchy of
grammars, from type 0 to type 3, is called the Chomsky hierarchy.
In a context-free grammar, a single nonterminal symbol on the left of a
production can be replaced wherever it appears by the right side of the production. In a context-sensitive grammar, a given nonterminal symbol can perhaps be replaced only if it is part of a particular string (context)—hence the
names context-free and context-sensitive. It is clear that any regular grammar
is also context-free, and any context-free grammar is also context-sensitive.
The grammar of Example 49 is regular (the two productions have the single
nonterminal S on the left, and on the right either 1—a terminal—or 0S—a terminal followed by a nonterminal). Both grammars of Example 51 are contextfree but not regular (again the single nonterminal S appears on the left of all
productions, but the right sides consist of three symbols or two nonterminals
or two terminals, respectively). The grammar of Example 52 is context-sensitive but not context-free (the productions do not shrink any strings, but some
left sides have multiple symbols). The grammars of Example 53 and Example
54 are context-free but not regular (for example, the first three productions of
Example 54 violate the requirement for a regular grammar). Finally, the grammar of Example 57 is a type 0 grammar, but it is not context-sensitive (for
example, the production EB S 0 is a “shrinking” production; also, the erasing
convention is violated).
Definition LAnGuAGE tyPEs
A language is type 0 (context-sensitive, context-free, or regular) if it can be
generated by a type 0 (context-sensitive, context-free, or regular) grammar.
Because of the relationships among the four grammar types, we can classify
languages as shown in Figure 9.26. Thus, any regular language is also context-free
because any regular grammar is also a context-free grammar, and so on. However,
although it turns out to be true, we do not know from what we have done that these
sets are properly contained in one another. For example, the language L described
in Example 57 was generated in that example by a grammar that was type 0 but
not context-sensitive, but that does not imply that L itself falls into that category.
Different grammars can generate the same language.