BCS402 Theory of Automata and Formal Languages Syllabus
AKTU B.Tech · 4th Semester · Unit-wise syllabus (effective 2023-24)
BCS402 Theory of Automata and Formal Languages (also written as KCS402) is a subject in Semester 4 of the AKTU B.Tech programme, prescribed by Dr. A.P.J. Abdul Kalam Technical University. It carries 4 credits with an L-T-P of 3-1-0. The syllabus is divided into 5 units: Basic Concepts and Automata Theory, Regular Expressions and Languages, Regular and Non-Regular Grammars. The complete unit-wise topic list, course outcomes and reference books are given below, taken from the official AKTU syllabus effective from 2023-24.
BCS402 Subject Details
| Subject Code | BCS402 / KCS402 |
|---|---|
| Subject Name | Theory of Automata and Formal Languages |
| University | Dr. A.P.J. Abdul Kalam Technical University (AKTU) |
| Course | B.Tech (Bachelor of Technology) |
| Year / Semester | 2nd Year · 4th Semester |
| Credits | 4 |
| L-T-P | 3-1-0 |
| Total Units | 5 |
| Scheme Effective From | 2023-24 |
| Last Verified | 2026-08-15 |
BCS402 Theory of Automata and Formal Languages Unit-Wise Syllabus
Official AKTU syllabus (effective 2023-24) — 5 units.
Unit 1: Basic Concepts and Automata Theory
Basic Concepts and Automata Theory: Introduction to Theory of Computation- Automata, Computability and Complexity, Alphabet, Symbol, String, Formal Languages, Deterministic Finite Automaton (DFA)- Definition, Representation, Acceptability of a String and Language, Non Deterministic Finite Automaton (NFA), Equivalence of DFA and NFA, NFA with ε-Transition, Equivalence of NFA’s with and without ε-Transition, Finite Automata with output- Moore Machine, Mealy Machine, Equivalence of Moore and Mealy Machine, Minimization of Finite Automata.
Unit 2: Regular Expressions and Languages
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
Unit 3: Regular and Non-Regular Grammars
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 4
Push Down Automata and Properties of Context Free Languages: Nondeterministic Pushdown Automata (NPDA)- Definition, Moves, A Language Accepted by NPDA, Deterministic Pushdown Automata(DPDA) and Deterministic Context free Languages(DCFL), Pushdown Automata for Context Free Languages, Context Free grammars for Pushdown Automata, Two stack Pushdown Automata, Pumping Lemma for CFL, Closure properties of CFL, Decision Problems of CFL, Programming problems based on the properties of CFLs.
Unit 5
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.
BCS402 Course Outcomes
- CO 3 At the end of course , the student will be able to understand
- CO 5 Analyse and design finite automata, pushdown automata, Turing machines, formal languages, K4, K6
- and grammars
- Analyse and design, Turing machines, formal languages, and grammars K4, K6
- Demonstrate the understanding of key notions, such as algorithm, computability, decidability, K1, K5
- and complexity through problem solving K2,K3
- Prove the basic results of the Theory of Computation.
- State and explain the relevance of the Church-Turing thesis. K1, K5
BCS402 Reference Books
- Introduction to Automata theory, Languages and Computation, J.E.Hopcraft, R.Motwani, and Ullman. 2nd
- 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
Frequently Asked Questions about BCS402
What is the syllabus of BCS402 Theory of Automata and Formal Languages?
The AKTU BCS402 Theory of Automata and Formal Languages syllabus is divided into 5 units: Basic Concepts and Automata Theory; Regular Expressions and Languages; Regular and Non-Regular Grammars. The complete topic list for each unit is published on this page, taken from the official Dr. A.P.J. Abdul Kalam Technical University syllabus effective from 2023-24.
How many units are there in BCS402?
BCS402 Theory of Automata and Formal Languages has 5 units in the AKTU syllabus, with an L-T-P (Lecture-Tutorial-Practical) structure of 3-1-0 and 4 credits.
Is BCS402 the same subject as KCS402?
Yes. AKTU renumbered its B.Tech subject codes from the 2022-23 session onwards, so the same subject appears as BCS402 and KCS402 depending on the scheme year. The syllabus content is the same.
Which semester is BCS402 taught in?
BCS402 Theory of Automata and Formal Languages is taught in Semester 4 of the 2nd year of the AKTU B.Tech programme.
How many credits is BCS402 worth?
BCS402 Theory of Automata and Formal Languages carries 4 credits in the AKTU evaluation scheme, with an L-T-P of 3-1-0.
Where can I download BCS402 previous year question papers?
All AKTU BCS402 Theory of Automata and Formal Languages previous year question papers are available to download free on Ryzenstudy, with no login or registration required.
Is this the official AKTU syllabus for BCS402?
Yes. Every topic on this page is taken from the official Dr. A.P.J. Abdul Kalam Technical University syllabus document (AKTU B.Tech 2nd Year CSE Syllabus), effective from 2023-24. A direct link to the original AKTU PDF is provided at the top of this page. Last verified on 2026-08-15.
Related AKTU Syllabus
Source: Dr. A.P.J. Abdul Kalam Technical University official syllabus — AKTU B.Tech 2nd Year CSE Syllabus, effective from 2023-24. Ryzenstudy is not affiliated with AKTU. Content last verified on 2026-08-15.