Theory of Computation
Machines and Models
Description
Finite State Machines: Alphabet, String, Formal and Natural Language, Operations, Definition and Design DFA (Deterministic Finite Automata), NFA (Non Deterministic Finite Automata), Equivalence of NFA and DFA: Conversion of NFA into DFA, Conversion of NFA with epsilon moves to NFA, Minimization of DFA, Definition and Construction of Moore and Mealy Machines, Inter-conversion between Moore and Mealy Machines. Minimization of Finite Automata. (Construction of Minimum Automaton)
Regular Expression and Regular Grammar: Definition and Identities of Regular Expressions, Construction of Regular Expression of the given Language, Construction of Language from the RE, Conversion of FA to RE using Arden’s Theorem, Inter-conversion RE to FA, Pumping Lemma for RL, Closure properties of RLs, Regular grammar, Equivalence of RG ( RLG and LLG) and FA
Context Free Grammar and Languages: Introduction, Formal Definition of Grammar, Notations, Derivation Process: Leftmost Derivation, Rightmost Derivation, Derivation Trees, Construction of Context-Free Grammars and Languages, Pumping Lemma for CFL, Simplification of CFG, Normal Forms (CNF and GNF), Chomsky Hierarchy
Pushdown Automata: Introduction and Definition of PDA, Construction of PDA, Acceptance of CFL, Equivalence of CFL and PDA: Inter-conversion , Introduction of DCFL and DPDA, Enumeration of properties of CFL, Context Sensitive Language, Linear Bounded Automata
Turing Machines: Formal definition of a Turing Machine, Design of TM, Computable Functions, Church’s hypothesis, Counter machine, Variants of Turing Machines: Multi-tape Turing machines, Universal Turing Machine
Decidability and Un-Decidability: Decidability of Problems, Halting Problem of TM, Un-Decidability: Recursive enumerable language, Properties of recursive & non-recursive enumerable languages, Post Correspondence Problem, Introduction to Recursive Function Theory
What You Will Learn!
- Construction of finite state machines to solve problems in computing
- Regular expressions for the formal languages
- Construct and analyze Push Down, Turing Machine, Linear Bounded Automata for formal languages
- Understanding of the Chomsky Hierarchy
- Decidability and un-decidability problems
Who Should Attend!
- Undergraduate and Post Graduate Students