Theory of Automata and Formal Languages (B.Tech)

Finite automata, regular expressions, context-free grammars, pushdown automata and Turing machines.

6 MonthsDuration 5Chapters29Topics

Enquire now

Syllabus · पाठ्यक्रम

Download PDF

01Unit 1: Finite Automata 6 topics

Alphabet, strings and languages
Deterministic finite automata (DFA)
Non-deterministic finite automata and NFA to DFA conversion
NFA with epsilon moves
Mealy and Moore machines
Minimisation of DFA and Myhill-Nerode theorem

02Unit 2: Regular Expressions and Languages 6 topics

Regular expressions and transition graphs
Kleene's theorem: FA to RE and RE to FA
Arden's theorem
Algebraic laws of regular expressions
Pumping lemma for regular languages
Closure and decision properties

03Unit 3: Grammars and Context-Free Languages 6 topics

Context-free grammars, derivations and parse trees
Ambiguity
Regular grammars (right and left linear)
Chomsky hierarchy
Simplification of CFG, CNF and GNF
Closure properties and pumping lemma for CFLs

04Unit 4: Pushdown Automata 5 topics

PDA definition and instantaneous description
Acceptance by final state and by empty stack
Deterministic PDA
Equivalence of PDA and CFG
Two-stack PDA

05Unit 5: Turing Machines and Undecidability 6 topics

Turing machine model and construction
Variants of Turing machines and universal TM
TM as computer of integer functions
Linear bounded automata
Church's thesis, recursive and recursively enumerable languages
Halting problem and Post's correspondence problem

About

You will be able to

Design DFA and NFA for given languages and convert NFA to DFA
Minimise DFA and design Mealy and Moore machines
Convert between finite automata and regular expressions (Arden's theorem) and use the pumping lemma
Write context-free grammars, remove ambiguity and convert to CNF and GNF
Design pushdown automata and relate them to CFGs
Design Turing machines and explain decidability, the halting problem and PCP

Who it is for

B.Tech Computer Science & Engineering, Information Technology students of Semester 4 (AKTU)
Students of other universities studying the same subject who want unit-wise coaching

What you need

Discrete Structures and Theory of Logic (sets, relations, proofs)

Questions

Which syllabus does the Theory of Automata and Formal Languages course follow?

It follows the AKTU (Dr. A.P.J. Abdul Kalam Technical University, Lucknow) B.Tech syllabus for Theory of Automata and Formal Languages. If your own university's syllabus differs, the centre follows your university syllabus.

Will this help in the university examination?

Yes. Teaching is unit-wise as per the AKTU scheme, with previous-year question practice, MCQ tests and doubt sessions before the semester exam.

This subject feels abstract. How is it taught?

Every concept is shown with step-by-step machine design (state diagrams and transition tables) and many solved exam questions.