Theory Of Computation
This is a course in 5th semester of B. Tech under BPUT. Mostly it is offered as an compulsory subject for the students of pre-final year in Computer Science and Information Technology branches. The subject basically consists of the following topic :
- Mathematical Prelimes
- Introduction to Automata
- Deterministic Finite Automata (DFA)
- Non Deterministic Finite Automata (NFA)
- Non Deterministic Finite Automata with e-moves (e-NFA)
- Formal Language and Grammar
- Formal Language
- Formal Grammar
- Relation between Language and Grammar
- Chomsky Classification.
- Pushdown Automata (PDA) and Context-Free Language (CFG)
- PDA and its acceptability
- Relationship between PDA and CFG
- Turing Machine and Type-0 Language
There are a handful of books that student can select as their material for the exam. Few out of them are as follow:
Text Book :- Introduction to Automata Theory
Languages, and Computation, by J.E.Hopcroft, R.Motwani & J.D.Ullman (3rd
Edition) – Pearson Education
- Theory of Computer Science (Automata
Language & Computations), by K.L.Mishra & N. Chandrashekhar, PHI.