DBATU · Third Year B.Tech Computer Engineering · NEP 2020
Theory of Computations
26AF1245PC502 · Semester V · 3 credits · Continuous assessment 20 + mid-semester 20 + end-semester 60
Unit 1: Finite Automata
8 hoursDFA and NFA, their languages and equivalence; applications; epsilon transitions and their elimination; minimising DFA; Moore and Mealy machines and their inter-conversion.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
Unit 2: Regular Expressions and Regular Grammars
6 hoursIdentities of regular expressions; converting between DFA and regular expressions; regular grammars and finite automata; the pumping lemma and closure properties of regular languages.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Regular expressions
- Conversions between regular expressions and finite automata
- Regular grammars and their equivalence with FA
- Pumping lemma for regular languages
- Closure and decision properties of regular languages
Unit 3: Context-Free Grammars
6 hoursDerivation trees, sentential forms and leftmost and rightmost derivations; ambiguity; minimising CFGs; CNF and GNF; the pumping lemma and properties of CFLs.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Context-free grammars and derivations
- Ambiguous grammars
- Simplification of CFGs
- Chomsky and Greibach normal forms
- Pumping lemma for context-free languages
Unit 4: Pushdown Automata and Turing Machines
8 hoursPDA model and acceptance by final state and by empty stack; equivalence of CFG and PDA; Turing machines, their languages, TMs as acceptors and as computers of integer functions; types of TMs.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
Unit 5: Recursive and Recursively Enumerable Languages
6 hoursProperties of recursive and r.e. languages; the universal TM; the halting problem and undecidable problems; context-sensitive languages and LBAs; the Chomsky hierarchy; decidability and the undecidability of PCP.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Recursive and recursively enumerable languages
- Universal Turing machine and the Church–Turing thesis
- Decidability and the halting problem
- Context-sensitive languages and linear bounded automata
- Chomsky hierarchy and applications of CFGs
- Post correspondence problem
Unit contents are summarised from the official DBATU syllabus . AiCanCode.org is not affiliated with Dr. Babasaheb Ambedkar Technological University (DBATU).