Theory of Computation for pune university 3rd Edition

Table of Contents Basic Mathematical Objects? Sets, Logic, Functions, Relations, Languages : Languages in abstract, Defining languages, Kleene closure. Recursive Definitions : New method for defining languages, Important languages. Finite Automata : An informal picture of FA, Deterministic finite automaton (DFA) : How a DFA processes strings, Simpler notations for DFA, Extending the transition function to strings, The language of DFA, Non-deterministic finite automaton (NFA) : NFA, Extended transition function, The language of an NFA, Equivalence of NFA and DFA, FA with e-transitions: Use of e-transitions, NFA with e, E-closures, Extended transitions and languages for e-NFA, Eliminating -transitions-Con version of NFA with e to NFA without e, Conversion of NFA without e to DFA, Conversion of NFA with 6 to DFA (direct method), FA with output : Moore and Mealy machines - Definition, Models, Inter-conversion. ? Regular Expressions (RE) and Languages? Regular expressions - Operators of RE, Building RE, Precedence of operators, Algebraic laws for RE, Arden's theorem, FA and RE : DFA to RE, RE to DFA (RE to s-NFA & e-NFA to DFA and RE to DFA-direct method), FA limitations, Properties of regular languages : Pumping lemma for regular languages, closure and decision properties of regular languages, Equivalence and minimization of automata, Application of RE : Regular expressions in Unix, GREP utilities of Unix, Lexical analysis and finding patterns in text. ? Context Free Grammars (CFG) and Languages? Context free grammar - Definition, Derivations, Languages of a grammar, Sentential form, Parse tree- Inference, Derivation and parse tree, From inference to tree, Ambiguity in grammars and languages : Removal of ambiguity, Inherent ambiguity, Properties of CFL- Normal forms- Chomsky Normal Form and Greibach Normal Form(GNF), Eliminating unit productions, Useless production, Useless symbols, and e-productions, Regular grammar - Definition, Le