# Introduction To

Theory Of Computation

The Theory of Computation is a scientific discipline concerned with the study of general properties of computation be it natural, man-made, or imaginary. Most importantly, it aims to understand the nature of efficient computation. In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm.

The theory of computation can be considered the creation of models of all kinds in the field of computer science. Therefore, mathematics and logic are used. In the last century it became an independent academic discipline and was separated from mathematics.

# Course Structure

## Regular Languages and Finite Automata

- Theory of Computation | Finite Automata Introduction
- Arden’s Theorem and Challenging Applications | Set 2
- Theory of Computation | L-graphs and what they represent
- Theory of Computation | Hypothesis (language regularity) and algorithm (L-graph to NFA)
- Regular Expressions, Regular Grammar and Regular Languages
- How to identify if a language is regular or not
- Theory of Computation | Arden’s Theorem
- TOC | Designing Finite Automata from Regular Expression (Set 1)
- Star Height of Regular Expression and Regular Language
- Theory of Computation | Generating regular expression from finite automata
- TOC | Designing Deterministic Finite Automata (Set 1)
- TOC | Designing Deterministic Finite Automata (Set 2)
- DFA for Strings not ending with “THE”
- DFA of a string with at least two 0’s and at least two 1’s
- DFA for accepting the language L = { anbm | n+m=even }
- DFA machines accepting odd number of 0’s or/and even number of 1’s
- DFA of a string in which 2nd symbol from RHS is ‘a’
- TOC | Union process in DFA
- TOC | Concatenation process in DFA
- DFA in LEX code which accepts even number of zeros and even number of ones
- Theory of Computation | Conversion from NFA to DFA
- Program to Implement NFA with epsilon move to DFA Conversion
- Theory of Computation | Minimization of DFA
- TOC | Complementation process in DFA
- TOC | Kleene’s Theorem Part-1
- Mealy and Moore Machines
- Difference between Mealy machine and Moore machine

## Context Free Grammar and Context Free Languages

- Theory of Computation | Relationship between grammar and language
- Simplifying Context Free Grammars
- Theory of Computation | Closure Properties of Context Free Languages
- Theory of Computation | Union & Intersection of Regular languages with CFL
- Converting Context Free Grammar to Chomsky Normal Form
- Converting Context Free Grammar to Greibach Normal Form
- Theory of Computation | Pumping Lemma
- Check if the language is Context Free or Not
- Ambiguity in Context free Grammar and Context free Languages
- Theory of Computation | Operator grammar and precedence parser
- TOC | Context-sensitive Grammar (CSG) and Language (CSL)

## Pushdown Automata

- Theory of Computation | Pushdown Automata
- Pushdown Automata Acceptance by Final State
- Construct Pushdown Automata for given languages
- Construct Pushdown Automata for all length palindrome
- Detailed Study of PushDown Automata
- NPDA for accepting the language L = {an bm cn | m,n>=1}
- NPDA for accepting the language L = {an bn cm | m,n>=1}
- NPDA for accepting the language L = {an bn | n>=1}
- NPDA for accepting the language L = {am b(2m) | m>=1}
- NPDA for accepting the language L = {am bn cp dq | m+n=p+q ; m,n,p,q>=1}
- Construct Pushdown automata for L = {0n1m2m3n | m,n ≥ 0}
- NPDA for accepting the language L = {ambnc(m+n) | m,n ≥ 1}
- NPDA for accepting the language L = {amb(m+n)cn | m,n ≥ 1}
- NPDA for accepting the language L = {a2mb3m | m ≥ 1}
- NPDA for accepting the language L = {amb(2m+1) | m ≥ 1}
- NPDA for accepting the language L = {aibjckdl | i==k or j==l,i>=1,j>=1}
- Construct Pushdown automata for L = {a(2*m)c(4*n)dnbm | m,n ≥ 0}
- Construct Pushdown automata for L = {0n1m2(n+m) | m,n ≥ 0}
- NPDA for L = {0i1j2k | i==j or j==k ; i , j , k >= 1}
- NPDA for accepting the language L = {anb(2n) | n>=1} U {anbn | n>=1}
- NPDA for the language L ={w∈ {a,b}*| w contains equal no. of a’s and b’s}
- Context free languages and Push-down automata

## Turing Machine

- Turing Machine
- Turing Machine for addition
- Turing machine for subtraction | Set 1
- Turing machine for multiplication
- Turing machine for copying data
- Construct a Turing Machine for language L = {0n1n2n | n≥1}
- Construct a Turing Machine for language L = {wwr | w ∈ {0, 1}}
- Construct a Turing Machine for language L = {ww | w ∈ {0,1}}
- Construct Turing machine for L = {an bm a(n+m) | n,m≥1}
- Construct a Turing machine for L = {aibjck | i*j = k; i, j, k ≥ 1}
- Turing machine for 1’s and 2’s complement
- Recursive and Recursive Enumerable Languages
- Turing Machine for subtraction | Set 2
- Theory of computation | Halting Problem
- Theory of Computation | Applications of various Automata
- TOC | Turing Machine as Comparator
- Recursively enumerable sets and Turing machines

## Decidability

- Theory of computation | Decidable and undecidable problems
- Theory of Computation | Decidability and Undecidability
- Undecidability and Reducibility
- NP-Completeness | Set 1 (Introduction)
- Proof that Hamiltonian Path is NP-Complete
- Proof that vertex cover is NP complete
- Theory of computation | Computable and non-computable problems