This course presents a study of Finite State Machines and their languages. It covers finite state automata, regular expressions, context free grammars, design of Push-down automata and Turing Machines, and basics of undecidability and intractability.
Introduce concepts of the models of computation and formal language approach to computationIntroduce concepts in automata theory and theory of computationDesign different finite state machines and grammars and recognizers for different formal languagesIdentify different formal language classes and their relationshipsDetermine the decidability and intractability of computational problems
Review of Set Theory, Logic, Functions, Proofs, Automata, Computability and Complexity: Complexity Theory, Computability Theory, Automata Theory, Basic concepts of Automata Theory: Alphabets, Power of Alphabet, Kleen Closure Alphabet, Positive Closure of Alphabet, Strings, Empty String, Substring of a string, Concatenation of strings, Languages, Empty Language
Introduction to Finite Automata, Introduction of Finite State Machine, Deterministic Finite Automata (DFA), Notations for DFA, Language of DFA, Extended Transition Function of DFA, Non-Deterministic Finite Automaton (NFA), Notations for NFA, Language of NFA, Extended Transition, Equivalence of DFA and NFA, Subset-Construction, Reduction of NFA to DFA, Theorems for equivalence of Language accepted by DFA and NFA, Finite Automaton with Epsilon Transition (ε-NFA), Epsilon Closure, Removing Epsilon Transition, Equivalence of NFA and ε-NFA, Equivalence of DFA and ε-NFA, Finite State Machines with output: Moore machine and Mealy Machines
Regular Expressions, Regular Operators, Regular Languages and their applications, Algebraic Rules for Regular Expressions, Equivalence of Regular Expression and Finite Automata, Reduction of Regular Expression to ε–NFA, Conversion of DFA to Regular Expression, Properties of Regular Languages, Pumping Lemma, Application of Pumping Lemma, Closure Properties of Regular Languages (Union, Intersection, Complement), Minimization of Finite State Machines: Table Filling Algorithm
Introduction to Context Free Grammar (CFG), Components of CFG, Use of CFG, Context Free Language (CFL), Types of derivations: Bottomup and Topdown approach, Leftmost and Rightmost, Language of a grammar, Parse tree and its construction, Ambiguous grammar, Using parse tree to show ambiguity, Regular Grammars: Right Linear and Left Linear, Equivalence of regular grammar and finite automata, Simplification of CFG: Removal of Useless symbols, Nullable Symbols, Unit Productions, Chomsky Normal Form (CNF), Greibach Normal Form (GNF), Backus-Naur Form (BNF), Context Sensitive Grammar, Chomsky Hierarchy, Pumping Lemma for CFL, Application of Pumping Lemma, Closure Properties of CFL
Introduction to Push Down Automata (PDA), Representation of PDA, Operations, Instantaneous Description, Deterministic and Non-Deterministic PDA, Acceptance of strings by PDA, Language of PDA, Construction of PDA by Final State, Construction by Empty Stack, Conversion between Final State and Empty Stack, Conversion of CFG to PDA, Conversion of PDA to CFG
Introduction to Turing Machines (TM), Notations, Language of TM, Instantaneous Description, Acceptance of a string, TM as Language Recognizer, Computing Function, TM with Storage in State, TM as enumerator, TM as Subroutine, TM with Multiple Tracks, Multiple Tapes, Equivalence of Multitape-TM and Multitrack-TM, Non-Deterministic Turing Machines, Restricted Turing Machines, Church-Turing Thesis, Universal Turing Machine, Turing Machine and Computers, Encoding of Turing Machine, Enumerating Binary Strings, Codes of TM, Universal TM for encoding of TM
Computational Complexity, Time and Space complexity of a Turing Machine, Intractability, Complexity Classes, Problem types: Abstract, Decision, Optimization, Reducibility, Turing Reducible, Circuit Satisfiability, Cook’s Theorem, Undecidability, Undecidable Problems: Post’s Correspondence Problem, Halting Problem and its proof, Undecidable Problems about Turing Machines
Design and implementation of finite state machines like DFA, NFA, PDA, and Turing MachineConstruction of Tokenizers/Lexers for some language using regex and Perl or other high-level language