PAHSU · Second Year B.Tech. Artificial Intelligence and Data Science · NEP 2020
Theory of Computation
ADPCC-05 · Semester IV · 3 credits · ISE 30 + ESE 70
Unit 1: Regular Expressions
6 hoursRegular expressions and the corresponding regular languages, with examples and applications; unions, intersections and complements of regular languages.
Examined in the 70-mark end-semester paper
- Alphabets, strings and languages
- Regular expressions and identities
- Closure properties of regular languages
Unit 2: Finite Automata
10 hoursFinite automata: definition and representation; nondeterministic FA and NFA with Λ-transitions; equivalence of DFA and NFA; Kleene's theorem; minimising the number of states; Moore and Mealy machines.
Examined in the 70-mark end-semester paper
- Deterministic finite automata
- NFA and ε-NFA
- Equivalence of NFA and DFA
- Converting RE to FA
- Arden's theorem: FA to RE
- Minimisation of DFA
- Moore and Mealy machines
Unit 3: Grammars and Languages
7 hoursTypes of grammars and languages; derivation trees and ambiguity; Chomsky normal form; union, concatenation and star of CFLs; eliminating Λ-productions, unit productions and useless variables from a CFG.
Examined in the 70-mark end-semester paper
- Chomsky hierarchy
- Derivation trees, sentential forms and ambiguity
- Simplification of CFGs
- Chomsky and Greibach normal forms
Unit 4: Pushdown Automata
6 hoursDefinition of the PDA, deterministic PDAs and types of acceptance; equivalence of CFGs and PDAs.
Examined in the 70-mark end-semester paper
- Pushdown automata and acceptance
- Deterministic pushdown automata
- Equivalence of CFG and PDA
Unit 5: Context-Free and Non-Context-Free Languages
5 hoursThe pumping lemma for CFLs with examples; intersections and complements of CFLs.
Examined in the 70-mark end-semester paper
- Pumping lemma for context-free languages
- Closure properties of context-free languages
Unit 6: Turing Machines
7 hoursModels of computation; the Turing machine as a language acceptor; combining Turing machines.
Examined in the 70-mark end-semester paper
- Church–Turing thesis
- Turing machines and their design
- Recursive and recursively enumerable languages
Unit 7: Variations in Turing Machines
4 hoursTMs with doubly infinite tapes, multitape and nondeterministic TMs, the universal TM; undecidability; time- and space-bounded computation.
Examined in the 70-mark end-semester paper
- Variants of Turing machines and the universal TM
- Decidability and the halting problem
- Complexity measures for Turing machines
- Space complexity classes: PSPACE, L and NL
Unit contents are summarised from the official PAHSU syllabus . AiCanCode.org is not affiliated with Punyashlok Ahilyadevi Holkar Solapur University (PAHSU).