Automata
This study material is classroom notes & handbook on Automata theory subject for Information technology (IT), Computer Science engineering, discrete mathematics & Mathematics students. It is part of engineering education which brings important topics, notes, news & blog on the subject. It covers 138 topics of Automata in detail. These 138 topics are divided into 5 units.
Introduction to Automata
Context free languages & grammar
Fixed point logic Unit
Automata and Logic
Temporal logic
- Introduction to automata theory and Formal Languages
- Finite automata
- Deterministic finite state automaton (DFA)
- Sets
- Relations and Functions
- Asymptotic Behavior of Functions
- Grammar
- Graphs
- Languages
- Nondeterministic finite automaton
- Strings and Languages
- Boolean Logic
- Orders for Strings
- Operations on languages
- Kleene Star, ‘∗’
- Homomorphism
- Machines
- The power of DFAs
- Machine types that accept non-regular languages
- Equivalence of NFA and DFA
- Regular Expressions
- Regular Expressions and Languages
- Building Regular Expressions
- NFAs to Regular Expression
- Two-way Finite Automata
- Finite Automata with Output
- Properties of regular sets (Languages)
- Pumping Lemma
- Closure properties of regular languages
- Myhill-Nerode Theorem-1
- Exampleof Non Deterministic Finite Automata
- Conversion of NFA to DFA
- Mealy and moore Machine
- Myhill-Nerode theorem
- Decision algorithms
- NFA with ε-moves
- Introduction to Context-Free Grammars
- Conversion of Left-linear Grammar into Right-Linear Grammar
- Derivation Tree
- Parsing
- Ambiguity
- Simplification of CFG
- Normal Forms
- Greibach Normal Form
- Pushdown Automata
- Transition Functions for NPDA
- Execution of NPDA
- Relation between pda and context free language
- CFG to NPDA
- NPDA to CFG
- Properties of context-free languages
- Proof of Pumping Lemma
- Usage of Pumping Lemma
- dicision Algorithms
- Binary Relation Basics
- Transitive, and Related Notions
- Equivalence (Preorder plus Symmetry)
- The Power Relation between Machines
- Error-correcting DFAs
- Ultimate Periodicity and DFAs
- A Taxonomy of Formal Languages and Machines
- Introduction to Push-down Automata
- Right- and Left-Linear CFGs
- Developing CFGs
- A Pumping Lemma for CFLs
- A Pumping Lemma for CFLs
- Context sensitive grammar and languages
- The chomsky hirarchy
- Unrestricted grammar
- Introduction to Complexity Theory
- polynomial time algorithm
- boolean satisfiablity
- Additional NP problem
- Formal systems
- Composition and recursion
- Ackermann's theorem
- Propositions
- Connectives
- Tautology, Contradiction and Contingency
- Logical Identities
- Logical inference
- Predicates and quantifiers
- Quantifiers and logical operators
- Normal forms
- Turing Machine
- Programming a Turing Machine
- Turing Machines as Transducers
- Complete language and functions
- Modification of turing machines
- Church-turing thesis
- Enumerating Strings in a Language
- Halting Problem
- Rice's Theorem
- Acceptance, Halting, Rejection
- NDTMs
- Simulations of turing machine
- Basic Undecidability Proofs
- Rice’s Theorem
- Greibach’s Theorem
- Post’s correspondence problem (PCP)
- PCP is undecidable
- Proof sketch of the undecidability of PCP
- Basic Notions in Logic including SAT
- Axiomatization of Propositional Logic
- First-order Logic (FOL) and Validity
- Examples of interpretations
- Validity of first-order logic is undecidable
- Properties of Boolean Formulas
- Overview of direct DNF to CNF conversion
- CNF-conversion using gates
- DIMACS file encoding
- Unsatisfiable CNF instances
- 3-CNF, =-satisfiability, and general CNF
- 2-CNF satisfiability
- DFA for Presburger Arithmetic
- Presburger Formulas and DFAs
- Encoding conventions
- Conversion algorithm: Presburger formulas to automata
- Pitfalls to Avoid
- An Introduction to Model Checking
- Reactive Computing Systems
- Model checking vs. testing
- Buchi automata, and Verifying Safety and Liveness
- Dining Philosophers
- Model (proctype) and property (never) automata
- Temporal Logics
- Computations vs. computation trees
- Temporal formulas are Kripke structure classifiers
- LTL vs. CTL through an example
- LTL syntax
- CTL syntax