Proof: The language {
|
}
a b c n
n n n
≥ 0 is not context-free (which could be
proved using a pumping lemma).
It can be shown that it is context-sensitive by providing an approprite
grammar.
The productions of one such grammar is given here.
S
aABC
A aBC
bB
bb
S
aBC
CB
BC
bC
bc
A aABC
aB
ab
cC
cc
→
→
→
→
→
→
→
→
→
¨
THE O REM (III): Every context-sensitive language is recursive.
Proof: A context-sensitive grammar is noncontracting. Moreover, for any
integer n there are only a finite number of sentential forms of length n.
Therefore, for any string w we could set a bound on the number of derivation
steps required to generate w, hence a bound on the number of possible
derivations. The string w is in the language if and only if one of these
derivations produces w.
5.4 THE CHOMSKY HIERARCHY
The Chomsky Hierarchy, as originally defined by Noam Chomsky, comprises
four types of languages and their associated grammars and machines.
Lan guage
Gram mar
Machine
Exam ple
Reg u lar lan -
guage
Reg u lar gram mar
—Right-lin ear gram mar
—Left-lin ear gram mar
Deter min is tic
or
Nondeterministic
finite-state
accep tor
a
*
Con text-free
lan guage
Con text-free gram mar
Nondeterministic
pushdown
autom a ton
a
n b
n
Con text-sen si -
tive lan guage
Con text sen si tive
gram mar
Lin earbounded
autom a ton
a
n b
n c
n
Recur sively
enumerable
lan guage
Unre stricted gram mar
Turing
machine
Any
com put able
func tion
212
Theory of Automata, Formal Languages and Computation