Information Technology Reference
In-Depth Information
Chapter Notes
The concept of the finite-state machine is often attributed to McCulloch and Pitts [
211
].
The models studied today are due to Moore [
223
]andMealy[
215
]. The equivalence of
deterministic and non-deterministic FSMs (Theorem
4.4.1
) was established by Rabin and
Scott [
266
].
Kleene established the equivalence of regular expressions and finite-state machines. The
proof used in Theorems
4.4.1
and
4.4.2
is due to McNaughton and Yamada [
212
]. The
pumping lemma (Lemma
4.5.1
) is due to to Bar-Hillel, Perles, and Shamir [
28
]. The closure
properties of regular expressions are due to McNaughton and Yamada [
212
].
State minimization was studied by Huffman [
144
] and Moore [223]. The Myhill-Nerode
Theorem was independently obtained by Myhill [
227
] and Nerode [229]. Hopcroft [
139
]has
given an efficient algorithm for state miminization.
Chomsky [
68
,
69
] defined four classes of formal language, the regular, context-free, context-
sensitive, and phrase-structure languages. He and Miller [
71
] demonstrated the equivalence
of languages generated by regular grammars and those recognized by finite-state machines.
Chomsky introduced the normal form that carries his name [
69
]. Oettinger [233] introduced
the pushdown automaton and Schutzenberger [
305
], Chomsky [
70
], and Evey [
97
] indepen-
dently demonstrated the equivalence of context-free languages and pushdown automata.
Two efficient algorithms for parsing context-free languages were developed by Earley [
94
]
and Cocke (unpublished) and independently by Kasami [
162
]andYounger[
371
]. These are
cubic-time algorithms. Our formulation of the parsing algorithm of Section
4.11
is based
on Valiant's derivation [
342
] of the Cocke-Kasami-Younger recognition matrix, where he also
presents the fastest known general algorithm to parse context-free languages. The CFL pump-
ing lemma and the closure properties of CFLs are due to Bar-Hillel, Perles, and Shamir [
28
].
Myhill [
228
] introduced the deterministic linear-bounded automata and Landweber [
189
]
showed that languages accepted by linear-bounded automata are context-sensitive. Kuroda
[
184
] generalized the linear-bounded automata to be nondeterministic and established the
equivalence of such machines and the context-sensitive languages.
Search WWH ::
Custom Search