Theory of Computation (IT-503)
rgpv bhopal, diploma, rgpv syllabus, rgpv time table, how to get transcript from rgpv, rgpvonline,rgpv question paper, rgpv online question paper, rgpv admit card, rgpv papers, rgpv scheme
B.Tech RGPV notes AICTE flexible curricula Bachelor of technology
Course Objectives
Student learns some fundamental concepts in automata theory and designing of Finite Automata,
conversion NFA to DFA. Application of Finite Automata in computer science and real world.
Obtain minimized DFA and Application of regular expression and conversion from RE to Finite
Automata and Finite Automata to Regular Expression and Proving language are not regular.
Designing of CFG’s , Construction of parse trees, finding and removing ambiguity in grammars,
simplification of CFG, Conversion of grammar to Chomsky Normal Form ,Greibach normal form.
Designing problems on Pushdown Automata and conversion of grammar to PDA, PDA to Grammar.
Designing Turing machines, understanding the working of various types of Turing machines and study P
and NP type problem.
Syllabus
UNIT 1:
Introduction of the theory of computation, Finite state automata – description of finite automata, properties of
transition functions, Transition graph, designing finite automata, FSM, DFA, NFA, 2-way finite automata,
equivalence of NFA and DFA, Mealy and Moore machines.
UNIT 2:
Regular grammars, regular expressions, regular sets, closure properties of regular grammars, Arden’s theorem,
Myhill-Nerode theorem, pumping lemma for regular languages, Application of pumping lemma, applications of
finite automata, minimization of FSA.
UNIT 3:
Introduction of Context-Free Grammar - derivation trees, ambiguity, simplification of CFGs, normal forms of
CFGs- Chomsky Normal Form and Greibach Normal forms, pumping lemma for CFLs, decision algorithms for
CFGs, designing CFGs, Closure properties of CFL’s.
UNIT 4:
Introduction of PDA, formal definition, closure property of PDA, examples of PDA, Deterministic Pushdown
Automata, NPDA, conversion PDA to CFG, conversion CFG to PDA.
UNIT 5:
Turing machines - basics and formal definition, language acceptability by TM, examples of TM, variants of
TMs – multitape TM, NDTM, Universal Turing Machine, offline TMs, equivalence of single tape and multitape
TMs. Recursive and recursively enumerable languages, decidable and undecidable problems – examples,
halting problem, reducibility. Introduction of P, NP, NP complete, NP hard problems and Examples of these
problems.
NOTES
- Unit 1
- Unit 2
- Unit 3
- Unit 4
- Unit 5
Books Recommended
1. Daniel I.A. Cohen,“Introduction to Computer Theory”,Wiley India.
2. John E Hopcroft, Jeffrey D. Ullman and Rajeev Motwani, “Introduction to Automata Theory, Languages and
Computation”, Pearson Education.
3. K.L.P Mishra & N.Chandrasekaran,“Theory of Computer Science”, PHI Learning.
4. Peter Linz, “Introduction to Automata Theory and Formal Languages”, Narosa Publishing.
5. John C Martin, “Introduction to languages and the theory of computation”, TATA McGraw Hill.
Course Outcomes
At the completion of the course, students will be able to...
Convertbetween finite automata, regular grammars, and regular expression representations of regular
languages
Apply the pumping lemma for regular languages to determine if a language is regular
Convertbetweengrammars and push-down automata for context-free languages
Determine if a language is regular or context-free
Demonstrate that a grammar is ambiguous
Translate a context-free grammar from one form to another
Produce simple programs for a Turing Machine
Explain the concept of undecidability
List examples of undecidable problems
You May Also Like
- IT-501 - Operating System
- IT-502 - Computer Network
- IT-503 - Microprocessor & Interfacing
- IT-503 - Principles of programming Languages
- IT-504 - Artificial Intelligence
- IT-504 - E Commerce & Governance
- IT-504 - Java Programming
- IT-505 - Advanced Java Lab
- IT-506 - Soft Skills and Interpersonal Communication
- IT-507 - Evaluation of Internship-II
- IT-508 - Minor Project I/Seminar
