Theory of Computation syllabus
2019 PATTERN. This is the 2019 pattern syllabus, the latest SPPU has published on its site for Third Year Computer Engineering. A 2024 pattern syllabus for this year has not been published there yet, so confirm with your college which pattern applies to you.
310242 · Third Year Computer Engineering, SPPU 2019 pattern. Every unit, the marks scheme, course outcomes and books, copied from the official syllabus PDF.
Unit-wise syllabus
Formal Language Theory and Finite Automata
7 hoursFinite Automata (FA): An informal picture of FA, Finite State Machine (FSM), Language accepted by FA, Definition of Regular Language. FA without output: Deterministic and Nondeterministic FA (DFA and NFA), epsilon- NFA and inter-conversion. Minimization of DFAs. FA with output: Moore and Mealy machines -Definition, models, inter-conversion.
Regular Expressions (RE)
7 hoursIntroduction, Operators of RE, Precedence of operators, Algebraic laws for RE, Language to Regular Expressions, Equivalence of two REs. Conversions: RE to NFA, DFA, DFA to RE using Arden’s theorem, Pumping Lemma for Regular languages, Closure and Decision properties of Regular languages. Myhill-Nerode theorem.
Context Free Grammar (CFG) and Context Free Language(CFL)
7 hoursBasic Elements of Grammar, Formal Definition of Context Free Grammar, Sentential form, Derivation and Derivation Tree/ Parse Tree, Context Free Language (CFL), Ambiguous Grammar, writing grammar for language. Simplification of CFG: Eliminating Є-productions, unit productions, useless production, and useless symbols. Normal Forms: Chomsky Normal Form, Greibach Normal Form, Pumping Lemma for CFG, Closure properties of CFL, Decision properties of CFL, Chomsky Hierarchy, Cock-Younger-Kasami Algorithm.
Pushdown Automata (PDA)
7 hoursIntroduction, Formal definition of PDA, Equivalence of Acceptance by Final State and Empty stack, Non-deterministic PDA (NPDA), PDA and Context Free Language, Equivalence of PDA and CFG, PDA vs CFLs. Deterministic CFLs.
Turing Machines (TM)
7 hoursTuring Machine Model, Formal definition of Turing Machines, Language Acceptability by Turing Machines, Design of TM, Description of TM, Techniques for TM Construction, Computing function with Turing Machine, Variants of Turing Machines, Halting Problem of TM, Halting vs Looping, A Turing-unrecognizable language, Reducibility, Recursion Theorem. The Model of Linear Bounded Automata.
Computability and Complexity Theory
7 hoursComputability Theory: Decidable Problems and Un-decidable Problems, Church-Turing Thesis. Reducibility: Undecidable Problems that is recursively enumerable, A Simple Un-decidable problem. Complexity Classes: Time and Space Measures, The Class P, Examples of problems in P, The Class NP, Examples of problems in NP, P Problem Versus NP Problem, NP-completeness and NP- hard Problems.
Marks and credits
| Head | Marks | Credit |
|---|---|---|
| Mid-Sem (mid-semester exam) | 30 | 3 |
| End-semester exam | 70 |
Prerequisite: Discrete Mathematics (210241).
Course outcomes
- CO1Understand formal language, translation logic, essentials of translation, alphabets, language representation and apply it to design Finite Automata and its variants
- CO2Construct regular expression to present regular language and understand pumping lemma for RE
- CO3Design Context Free Grammars and learn to simplify the grammar
- CO4Construct Pushdown Automaton model for the Context Free Language
- CO5Devise Turing Machine for the different requirements outlined by theoretical computer science
- CO6Analyze different classes of problems, and study concepts of NP completeness
Books
Text books
- John E. Hopcroft, Rajeev Motwani, Jeffrey D.Ullman, “Introduction to Automata Theory Languagesand Computation”, Addison-Wesley,ISBN 0-201-44124-1
- Daniel Cohen, “Introduction to Computer Theory”, Wiley & Sons, ISBN 97881265133454
Reference books
- Sanjeev Arora and Boaz Barak, “Computational Complexity: A Modern Approach”, Cambridge University Press, ISBN: 0521424267 97805214242643
- John Martin, “Introduction to Languages and The Theory of Computation”, 2nd Edition, McGrawHill Education, ISBN-13: 978-1-25-900558-9, ISBN-10: 1-25-900558-5
- J.Carroll & D Long, “Theory of Finite Automata”, Prentice Hall, ISBN 0-13-913708-45
- Kavi Mahesh, “Theory of Computation: A Problem-Solving Approach”, Wiley India, ISBN1081265331106
- Michael Sipser, “Introduction to the Theory of Computation”, Cengage Learning, ISBN- 13: 97811331878137
- Vivek Kulkarni, “Theory of Computation”, Oxford University Press, ISBN 0-19-808458
FAQ
How many units are in Theory of Computation?
Theory of Computation (310242) has 6 units: Unit I Formal Language Theory and Finite Automata (7 h); Unit II Regular Expressions (RE) (7 h); Unit III Context Free Grammar (CFG) and Context Free Language(CFL) (7 h); Unit IV Pushdown Automata (PDA) (7 h); Unit V Turing Machines (TM) (7 h); Unit VI Computability and Complexity Theory (7 h).
What is the marks scheme for Theory of Computation?
The official Computer Engineering 2019 pattern syllabus lists mid-semester (Mid-Sem) for 30 marks and the end-semester exam for 70 marks, for 3 credits.
What should I know before Theory of Computation?
Prerequisite listed in the syllabus: Discrete Mathematics (210241).