AD-501 · Theory of Computation/Official Syllabus
Theory of Computation (AD-501) - Official Syllabus
1
Unit 1
Introduction of Automata Theory
- Review of Sets
- Mathematical formal proofs including proof by induction and by contradiction
- Introduction to languages, grammars and automata
- Alphabet
- Representation of language and grammar
- Types of Automata
- Finite Automata as a language acceptor and translator
- Moore machines and mealy machines
- composite machine
- Conversion from Mealy to Moore and vice versa
2
Unit 2
Types of Finite Automata
- Non Deterministic Finite Automata (NDFA)
- Deterministic finite automata machines
- conversion of NDFA to DFA
- minimization of automata machines
- regular expression
- applications of regular expressions
- Arden’s theorem
- Meaning of union, intersection, concatenation and closure
- 2 way DFA
3
Unit 3
Grammars
- Types of grammar
- context sensitive grammar
- context free grammar
- regular grammar
- Derivation trees
- ambiguity in grammar
- simplification of context free grammar
- conversion of grammar to automata machine and vice versa
- Chomsky hierarchy of grammar
- Chomsky normal form and Greibach normal form
4
Unit 4
Push down Automata
- example of PDA
- deterministic and non-deterministic PDAs
- Context Free Grammar
- Parsing
- Ambiguity
- Normal form of CFGs
- CFG to NPDA
- NPDA to CFGs
- CFG equivalent to PDA
- Petri nets model
5
Unit 5
Turing Machine
- Turing Machine as acceptor
- Recognizing a Language
- Universal TMs
- Linear Bounded Automata
- Context Sensitive Languages
- Recursive and Recursively Enumerable Languages
- Unrestricted Grammars
- Halting problem of Turing machine & the post correspondence problem
- Concept of Solvability and Unsolvability
- Church’s Thesis
- Complexity Theory – P and NP problems
Laboratory Experiments
- Design a Program for creating machine that accepts three consecutive one.
- Design a Program for creating machine that accepts the string always ending with 101.
- Design a Program for Mode 3 Machine
- Design a program for accepting decimal number divisible by 2.
- Design a program for creating a machine which accepts string having equal no. of 1’s and 0’s.
- Design a program for creating a machine which count number of 1’s and 0’s in a given string.
- Design a Program to find 2’s complement of a given binary number.
- Design a Program which will increment the given binary number by 1.
- Design a Program to convert NDFA to DFA.
- Design a Program to create PDA machine that accept the well-formed parenthesis.
- Design a PDA to accept WCWR where w is any string and WR is reverse of that string and C is a Special symbol.
- Design a Turing machine that’s accepts the following language anbncn where n>0.
Reference Books
- Introduction to Languages, Automata and Computation — Hopcroft, Ullman, Motwani — Pearson Education — 3rd Edition
- Introduction to Languages and the Theory of Computation — John C. Martin — Mc Graw Hill — Fourth Edition
- An Introduction to Formal Languages and Automata — Peter Linz — Jones and Bartlett — Sixth Edition
- Elements of Theory of Computation — Lewis, Papadimitiriou — Pearson Education — Second Edition
- Theory of Computer Science: Automata, Languages and Computation — K.L.P. Mishra, N. Chandrasekaran — Prentice Hall — Third Edition
- Introduction to Computer Theory — Cohen John — Wiley and Sons — Second Edition
- Theory of Computation — Wood — Harper & Row
Go to where you left off?
Quick Add to Notes
Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.
Create free accountHave an account? Log in
Notes Panel