Theory of Automata and Formal Languages detail syllabus for Computer Science Engineering (Cse), 2019-20 scheme is taken from AKTU official website and presented for AKTU students. The course code (KCS402), and for exam duration, Teaching Hr/Week, Practical Hr/Week, Total Marks, internal marks, theory marks, duration, and credits do visit complete sem subjects post given below.
For all other cse 4th sem syllabus for b.tech 2019-20 scheme aktu you can visit CSE 4th Sem syllabus for B.Tech 2019-20 Scheme AKTU Subjects. The detail syllabus for theory of automata and formal languages is as follows.
Unit I
For the complete syllabus, results, class timetable and more kindly download iStudy. It’s a lightweight, easy to use, no images, no pdfs platform to make student’s life easier.
Unit II
Regular Expressions and Languages: Regular Expressions, Transition Graph, Kleen’s Theorem, Finite Automata and Regular Expression-Arden’s theorem, Algebraic Method Using Arden’s Theorem, Regular and Non-Regular Languages-Closure properties of Regular Languages, Pigeonhole Principle, Pumping Lemma, Application of Pumping Lemma, Decidability-Decision properties, Finite Automata and Regular Languages, Regular Languages and Computers, Simulation of Transition Graph and Regular language.
Unit III
Regular and Non-Regular Grammars: Context Free Grammar(CFG)-Definition, Derivations, Languages, Derivation Trees and Ambiguity, Regular Grammars-Right Linear and Left Linear grammars, Conversion of FA into CFG and Regular grammar into FA, Simplification of CFG, Normal Forms-Chomsky Normal Form(CNF), Greibach Normal Form (GNF), Chomsky Hierarchy, Programming problems based on the properties of CFGs.
Unit IV
For the complete syllabus, results, class timetable and more kindly download iStudy. It’s a lightweight, easy to use, no images, no pdfs platform to make student’s life easier.
Unit V
Turing Machines and Recursive Function Theory : Basic Turing Machine Model, Representation of Turing Machines, Language Acceptability of Turing Machines, Techniques for Turing Machine Construction, Modifications of Turing Machine, Turing Machine as Computer of Integer Functions, Universal Turing machine, Linear Bounded Automata, Church’s Thesis, Recursive and Recursively Enumerable language, Halting Problem, Post’s Correspondance Problem, Introduction to Recursive Function Theory.
Course Outcomes:
- Analyse and design finite automata, pushdown automata, Turing machines, formal languages, and grammars.
- Analyse and design, Turing machines, formal languages, and grammars.
- Demonstrate the understanding of key notions, such as algorithm, computability, decidability, and complexity through problem solving.
- Prove the basic results of the Theory of Computation.
- State and explain the relevance of the Church-Turing thesis.
Reference Books:
- Introduction to Automata theory, Languages and Computation, J.E.Hopcraft, R.Motwani, and Ullman. 2nd edition, Pearson Education Asia.
- Introduction to languages and the theory of computation, J Martin, 3rd Edition, Tata McGraw Hill.
- Elements and Theory of Computation, C Papadimitrou and C. L. Lewis, PHI.
- Mathematical Foundation of Computer Science, Y.N.Singh, New Age Internationa.
For detail syllabus of all other subjects of B.Tech Cse, 2019-20 scheme do visit Cse 4th Sem syllabus for 2019-20 scheme.
Don’t forget to download iStudy for the latest syllabus, results, class timetable and more.