## Introduction to Formal Language TheoryFormal 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.

### Contents

FINITE AUTOMATA AND LINEAR GRAMMARS | 45 |

SOME BASIC PROPERTIES OF CONTEXTFREE LANGUAGES | 73 |

NORMAL FORMS FOR CONTEXTFREE GRAMMARS | 93 |

Copyright | |

10 other sections not shown

### Common terms and phrases

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