5.5 EXTENDING THE CHOMSKY HIERARCHY
So far we have discussed about other types of languages besides those in the
“classical Chomsky hierarchy. For example, we noted that deterministic
pushdown automaton were less powerful than nondeterministic pushdown
automata. The table below shows a table of some of the language classes we
have covered that fit readily into the hierarchy.
Lan guage
Machine
Reg u lar lan guage
Deter min is tic or Non-deter min is tic
finite-state accep tor
Deter min is tic con text-free lan guage Deter min is tic Pushdown Autom a ton
Con text-free lan guage
Non-deter min is tic pushdown Autom -
a ton
Con text-Sen si tive lan guage
Lin ear-bounded Autom a ton
Recur sive lan guage
Turing machine that halts
Recur sively enumerable lan guage
Turing machine
It should be noted that not all language classes fit into a hierarchy. When
linear languages are considered, they fit neatly between the regular languages
and the context-free languages. However there are languages that are linear but
not deterministic context-free, and there are languages that are deterministic
context-free but not linear.
5.6 UNRESTRICTED GRAMMAR
The grammars in the Chomsky hierarchy allows productions of the form
α β
→
where α and β are arbitrary strings of grammar symbols, with α λ
≠ .
These types of grammars as called “Unrestricted grammars”. The 4-tuple
notation G V T P S
= ( , , , ) is used for unrestricted grammars also.
L G
w w
T
S w
( ) { |
}
*
*
=
⇒
is in
and
⇒
* denotes the reflexive and transitive closure of the relation ⇒.
THE O REM (I): If L is L(G) for unrestricted grammar G V T P S
= ( , , , ) , then L
is an r.e. language.
THE O REM (II): If L is an r.e. language, then L L G
= ( ) for some unrestricted
grammar G.
Chomsky Hierarchy
213