Introduction to Formal Language Theory
Addison-Wesley Publishing Company, 1978 - Language Arts & Disciplines - 594 pages
Formal language theory was fist developed in the mid 1950's in an attempt to develop theories of natural language acquisition. It was soon realized that this theory (particularly the context-free portion) was quite relevant to the artificial languages that had originated in computer science. Since those days, the theory of formal languages has been developed extensively, and has several discernible trends, which include applications to the syntactic analysis of programming languages, program schemes, models of biological systems, and relationships with natural languages.
What people are saying - Write a review
We haven't found any reviews in the usual places.
FINITE AUTOMATA AND LINEAR GRAMMARS
SOME BASIC PROPERTIES OF CONTEXTFREE LANGUAGES
NORMAL FORMS FOR CONTEXTFREE GRAMMARS
10 other sections not shown
A-free accepted algorithm alphabet Association for Computing automata binary bounded canonical cross section Chomsky normal form completes the proof Computing Machinery consider construction context-sensitive grammar context-sensitive languages contradiction Corollary define Definition Let derivation trees deterministic context-free language dpda equivalent erasing exists finite automaton formal given grammar G Greibach normal form homomorphism implies induction hypothesis Induction step infinite Information and Control inherently ambiguous input integer Intuitively iteration theorem left recursive Lemma length Let G lg(a lg(w linear grammar LR(k node nondeterministic Note parse parser phrase-structure grammar Post Correspondence Problem prefix prefix-free Problem production Proof Let proof of Claim proof of Theorem Proof The argument Proposition Prove the following realtime recognition matrix recursive reduced context-free grammar regular set result right linear rule sentential form sequence Show stack strict deterministic grammar string subset Suppose symbol tape terminal transitive closure Turing machine unambiguous variables