Theory of Computation Notes, Micro syllabus, model Question solution ,past Question paper and more

Automata theory (also known as Theory Of Computation) is a theoretical branch of Computer Science and Mathematics, which mainly deals with the logic of computation with respect to simple machines, referred to as automata.

Automata* enables the scientists to understand how machines compute the functions and solve problems. The main motivation behind developing Automata Theory was to develop methods to describe and analyse the dynamic behavior of discrete systems.

Automata is originated from the word “Automaton” which is closely related to “Automation”.

Theory of Computation Notes

Micro Syllabus

Unit I: Basic Foundations

1.1. Review of Set Theory, Logic, Functions, Proofs

1.2. Automata, Computability and Complexity: Complexity Theory, Computability Theory,Automata Theory

1.3. Basic concepts of Automata Theory: Alphabets,Power of Alphabet, Kleene Closure Alphabet,Positive Closure of Alphabet, Strings, Empty String, Suffix, Prefix and Substring of a string,Concatenation of strings, Languages, Empty Language, Membership in Language

Unit II: Introduction to Finite Automata

2.1. Introduction to Finite Automata, Introduction of

Finite State Machine

2.2. 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

2.3. Equivalence of DFA and NFA, Subset-Construction

2.4. Method for reduction of NFA to DFA, Theorems for equivalence of Language accepted by DFA and NFA: For any NFA, N = (QN, ∑, N, q0, FN) accepting language L  ∑* there is a DFA D = (QD, ∑, D, q0’,FD) that also accepts L i.e. L (N) = L (D), A language L is accepted by some NFA if L is accepted by some DFA.

2.5. Finite Automaton with Epsilon Transition (ε -NFA), Notations for ε - NFA, Epsilon Closure of a State, Extended Transition Function of ε –

NFA, Removing Epsilon Transition using the concept of Epsilon Closure, Equivalence of NFA and ε –NFA, Equivalence of DFA and ε – NFA

2.6. Finite State Machines with output: Moore Machine and Mealy Machines, Illustration of the Moore and Mealy Machines

Unit III: Regular Expressions

3.1. Regular Expressions, Operators of Regular Expressions (Union, Concatenation, Kleene),Regular Languages and their applications,
Algebraic Rules for Regular Expressions

3.2. Equivalence of Regular Expression and Finite Automata, Reduction of Regular Expression to ε–NFA, Conversion of DFA to Regular
Expression, Arden’s Theorem

3.3. Properties of Regular Languages, Pumping Lemma for regular Expression, Application of Pumping Lemma, Closure Properties of Regular Languages over (Union, Intersection ,Complement), Minimization of Finite State Machines: Table Filling Algorithm