BAMU · Third Year B.E./B.Tech Computer Science and Engineering · NEP 2020
Theory of Computation
PCCT-4 · Semester V · 3 credits · CIA 40 + SEE 60
Module 1: Finite Automata and Formal Languages; Regular Expressions and Regular Languages
15 hoursDFA, NFA and NFA with ε-moves, NFA-to-DFA conversion, equivalence and minimisation of DFA, finite automata with output; regular expressions and their algebraic laws, equivalence with finite automata, Arden's theorem, the pumping lemma and closure properties of regular languages.
Examined in the 60-mark end-semester paper
Module 2: Context-Free Grammars and Languages; Pushdown Automata
15 hoursCFGs, derivations, parse trees and ambiguity, simplification, CNF and GNF; PDAs and their acceptance, equivalence of PDA and CFG, deterministic and non-deterministic PDAs, the pumping lemma for CFLs and linear bounded automata.
Examined in the 60-mark end-semester paper
- Context-free grammars and derivations
- Ambiguous grammars
- Simplification of CFGs
- Chomsky and Greibach normal forms
- Pushdown automata
- Equivalence of PDA and CFG
- Pumping lemma for context-free languages
- Context-sensitive languages and linear bounded automata
Module 3: Turing Machines and Computability; Decidability and Computational Complexity
15 hoursTuring machines and their design, random-access and non-deterministic TMs, the universal TM, the Church–Turing hypothesis and the halting problem; decidable and undecidable problems, recursive and recursively enumerable languages, PCP, P, NP, NP-complete and NP-hard problems.
Examined in the 60-mark end-semester paper
- Turing machines
- Designing Turing machines
- Variants of Turing machines
- Universal Turing machine and the Church–Turing thesis
- Decidability and the halting problem
- Recursive and recursively enumerable languages
- Post correspondence problem
- P, NP and NP-completeness
Module contents are summarised from the official BAMU syllabus . AiCanCode.org is not affiliated with Dr. Babasaheb Ambedkar Marathwada University (BAMU).