Your roadmap · आपका रोडमैप
- 1
Admission & first meetingप्रवेश और पहली मुलाकातEnquire at your nearest NDSS centre, meet the teacher, fix the batch time and get your study material.
- 2
Part 1 of the syllabusपाठ्यक्रम भाग 1Unit-wise coaching with notes and doubt classes.
Unit 1: Finite AutomataUnit 2: Regular Expressions and Regular LanguagesUnit 3: Context-Free Grammars and Languages
- 3
Part 2 of the syllabusपाठ्यक्रम भाग 2Unit-wise coaching with notes and doubt classes.
Unit 4: Pushdown AutomataUnit 5: Turing Machines and Undecidability
- 4
Unit tests & assignmentsयूनिट टेस्टRegular tests in the university / board pattern.
- 5
Semester 2 exam (university / board)विश्वविद्यालय / बोर्ड परीक्षाPrevious papers and full revision before the exam.
- 6
Online tests & resultऑनलाइन टेस्ट और रिज़ल्टTake the tests online; your marks and result show in your student login and at the centre.
Syllabus · पाठ्यक्रम
1 subject · 5 chapters · 29 topics
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 this course
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
Online tests & result
Practice and unit tests online; marks and result show in your student login and at the centre.
Student login →
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.
