Theory of Automata & Formal Languages (MCA)

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 (NFA) and epsilon-NFA
Equivalence of NFA and DFA: subset construction
Minimisation of DFA
Moore and Mealy machines and their conversion

02Unit 2: Regular Expressions and Regular Languages 6 topics

Regular expressions and identities
Arden's theorem
Conversion of finite automata to regular expressions and back
Pumping lemma for regular languages
Closure and decision properties of regular languages
Regular grammars

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

Chomsky hierarchy of grammars
Context-free grammars, derivations and parse trees
Ambiguity in grammars
Simplification: useless, null and unit productions
Chomsky normal form and Greibach normal form
Pumping lemma and closure properties of CFLs

04Unit 4: Pushdown Automata 5 topics

Definition and instantaneous description of a PDA
Acceptance by final state and by empty stack
Design of PDA for given languages
Equivalence of PDA and CFG
Deterministic PDA and deterministic CFLs

05Unit 5: Turing Machines and Undecidability 6 topics

Turing machine model and design
Variants: multi-tape and non-deterministic TM
Church-Turing thesis and universal TM
Recursive and recursively enumerable languages
Halting problem and undecidability
Post's correspondence problem

About

You will be able to

Design DFA and NFA for given languages and convert an NFA into a DFA
Minimise a DFA and design Moore and Mealy machines
Write regular expressions, convert between automata and regular expressions and apply Arden's theorem
Use the pumping lemma to prove that a language is not regular or not context-free
Simplify context-free grammars and convert them into CNF and GNF
Design pushdown automata and Turing machines for simple languages
Explain decidability, the halting problem and Post's correspondence problem

Who it is for

MCA students of Semester 2 (AKTU, Lucknow)
Students preparing for GATE / UGC-NET computer science who need theory of computation basics

What you need

Discrete mathematics: sets, relations, functions and proof by induction

Questions

Which syllabus does this Theory of Automata & Formal Languages course follow?

It follows the AKTU (Lucknow) MCA syllabus for Semester 2. If your own university's syllabus differs, the centre follows your university's syllabus and unit order.

This subject feels abstract. How is it taught?

Every topic is taught with drawn state diagrams and many solved design problems, then practised in short tests.

How are students tested at the centre?

Unit-wise MCQ tests, numerical / problem practice, previous AKTU question papers and a final mock paper before the semester exam.