Formal Languages and Computation : Models and Their Applications

Formal Languages and Computation: Models and Their Applications gives a clear, comprehensive introduction to formal language theory and its applications in computer science. It covers all rudimental topics concerning formal languages and their models, especially grammars and automata, and sketches the basic ideas underlying the theory of computatio INTRODUCTIONMathematical BackgroundLogic Sets and SequencesRelationsGraphsFormal Languages and Rewriting SystemsFormal LanguagesRewriting systemsSynopsis of the BookREGULAR LANGUAGES AND THEIR MODELS Models for Regular LanguagesFinite AutomataRestricted Finite AutomataRegular Expressions and their Equivalence with Finite AutomataImplementation of Finite AutomataIntroduction to Lexical AnalysisImplementation of a ScannerProperties of Regular LanguagesPumping Lemma for Regular LanguagesClosure PropertiesCONTEXT-FREE LANGUAGES AND THEIR MODELS Models for Context-Free LanguagesContext-Free GrammarsRestricted Context-Free GrammarsPushdown AutomataApplications of Models for Context-Free Languages: Syntax AnalysisIntroduction to Syntax AnalysisTop-Down ParsingBottom-Up ParsingProperties of Context-Free LanguagesPumping Lemma for Context-Free LanguagesClosure PropertiesTURING MACHINES AND COMPUTATIONTuring Machines and Their VariantsTuring Machines and Their LanguagesRestricted Turing MachinesUniversal Turing MachinesApplications of Turing Machines: Theory of ComputationComputabilityDecidabilityTuring Machines and General GrammarsGeneral Grammars and Their Equivalence with Turing MachinesContext-Sensitive Grammars and Linear-Bounded AutomataRelations between Language FamiliesCONCLUSION Concluding and Bibliographical RemarksSummaryModern TrendsBibliographical and Historical Remarks Formal Languages and Models and Their Applications gives a clear, comprehensive introduction to formal language theory and its applications in computer science. It covers all rudimental topics concerning formal languages and their models, especially grammars and automata, and sketches the basic ideas underlying the theory of computation, including computability, decidability, and computational complexity. Emphasizing the relationship between theory and application, the book describes many real-world applications, including computer science engineering techniques for language processing and their implementation. In short, this book represents a theoretically oriented treatment of formal languages and their models with a focus on their applications. It introduces all formalisms concerning them with enough rigors to make all results quite clear and valid. Every complicated mathematic