FREE
AKTU Theory of Computation (BMI013) Syllabus PDF – Integrated MCA 5th Semester
Theory of Computation BMI013
All syllabus, notes, question bank & PYQ for this subject
Free
Download now
- English
- Semester 5
- 0 downloads
- 0 views
Official AKTU syllabus of Theory of Computation (BMI013) for Integrated MCA 5th Semester. Read the unit-wise course content, course outcomes, evaluation pattern and recommended books online, or download the PDF.
Syllabus — Theory of Computation
Download PDFBMI013
Course Outcomes
At the end of course , the student will be able to understand
| CO1 | Explain the fundamentals of automata theory and construct DFA, NFA, and regular expressions for regular languages | K 2 |
| CO2 | Analyze regular languages using pumping lemma and design context-free grammars for context-free languages. | K 4 |
| CO3 | Design pushdown automata and relate them with context-free grammars for solving language recognition problems. | K 3 |
| CO4 | Explain Turing machines and evaluate computability and decidability of problems. | K 2 |
| CO5 | Analyze computational complexity of algorithms and distinguish between tractable and intractable problems. | K 4 |
Course Content
| Unit | Topic | Propose d Lecture |
|---|---|---|
| I | Introduction to Automata and Regular Language: Mathematical preliminaries, Alphabets, Strings, Languages, Deterministic finite Automata (DFA)-Formal Definition, Simplified notation: State transition graph, Transition table, Language of DFA, Nondeterministic finite Automata (NFA), NFA with epsilon transition, Language of NFA, Equivalence of NFA and DFA, Minimization of Finite Automata. | 08 |
| II | Regular Expression Languages and Context-Free Grammars: Regular expression (RE), Definition, Operators of regular expression and their precedence, Algebraic laws for Regular expressions, Kleen’s Theorem, Regular expression to FA, DFA to Regular expression, Arden Theorem, Non Regular Languages, Pumping Lemma for regular Languages, Closure properties of Regular Languages, Decision properties of Regular Languages, FA with output: Moore and Mealy machine, Equivalence of Moore and Mealy Machine, Applications and Limitation of FA. | 08 |
| III | Context free grammar (CFG) and Context Free Languages (CFL): Definition, Examples, Derivation, Derivation trees, Ambiguity in Grammar, Ambiguous to Unambiguous CFG, Useless symbols, Simplification of CFGs, Normal forms for CFGs: CNF and GNF, Closure proper ties of CFLs, Decision Properties of CFLs: Emptiness, Pumping lemma for CFLs. | 08 |
| IV | Pushdown Automata and Context-Free Languages: Push Down Automata (PDA): Description and definition, Instantaneous Description, Language of PDA, Acceptance by Final state, Acceptance by empty stack, Deterministic PDA, Equivalence of PDA and CFG, CFG to PDA and PDA to CFG, Two stack PDA. | 08 |
| V | Turing Machines and Computability: Turing machines (TM): Basic model, definition and representation, Instantaneous Description, Language acceptance by TM, Variants of Turing Machine, TM as Computer of Integer functions, Universal TM, Church’s Thesis, Recursive and recursively enumerable | 08 |
languages, Halting problem, Introduction to Undecidability, Undecidable problems about TMs. Post correspondence problem (PCP), Modified PCP, Introduction to recursive function theory
Suggested Readings
- Hopcroft, Ullman, “Introduction to Automata Theory, Languages and Computation”, Pearson Education.
- KLP Mishra and N. Chandrasekaran, “Theory of Computer Science: Automata, Languages and Computation”, PHI Learning Private Limited, Delhi India.
- Peter Linz, "An Introduction to Formal Language and Automata", Narosa Publishing house.
- YN Singh “Mathematical Foundation of Computer Science”, New Age International.
- Malviya, AK "Theory of Computation and Application", BPaperback Publications .
- Papadimitrou, C. and Lewis, CL, “Elements of the Theory of Computation”, Pearson Publication.
- K. Krithivasan and R. Rama; Introduction to Formal Languages, Automata Theory and Computation; Pearson Education.
- Harry R. Lewis and Christos H. Papadimitriou, Elements of the theory of Computation, Second Edition, Prentice-Hall of India Pvt. Ltd.
- Micheal Sipser, “Introduction of the Theory and Computation”, Thomson Learning.
- Katuri Viswanath, “Introduction to Mathematical Computer Science, An” Universities Press.
Ratings & Reviews
No reviews yet — share your experience with this item.