AKTU Theory of Automata and Formal Languages (BCS402) Question Bank with Solutions – B.Tech 2nd Year Sem 4

Download the AKTU Theory of Automata and Formal Languages (BCS402) question bank PDF for B.Tech 2nd Year, Semester IV students of Dr. A.P.J. Abdul Kalam Technical University (AKTU), Lucknow. It is prepared for Computer Science & Engineering and Allied Branches and focuses on DFA, NFA, regular expressions, context-free grammars, pushdown automata and Turing machines — everything you need for revision and the semester examination.

Question Bank Details

• Subject Code: BCS402
• Subject: Theory of Automata and Formal Languages
• Programme: B.Tech.
• Year: 2nd Year
• Semester: IV
• Branch: Computer Science & Engineering and Allied Branches
• University: AKTU, Lucknow
• Type: Question Bank
• Language: English
• Format: PDF

What This Question Bank Contains

• Unit-wise short-answer questions
• Unit-wise long-answer questions
• Previous-year questions with answers
• Most Important and Important questions
• Exam-oriented answers, diagrams and solved numerical problems
• AKTU-format sample model question paper

Unit-Wise Coverage

Unit I - Basic Concepts and Automata Theory

Introduction to Theory of Computation, automata, computability and complexity, alphabet, symbols and strings, formal languages, deterministic finite automata, nondeterministic finite automata, epsilon-NFA, equivalence of DFA and NFA, Moore and Mealy machines and minimisation of finite automata.

Unit II - Regular Expressions and Languages

Regular expressions, algebraic laws, transition graphs, Kleene's theorem, Arden's theorem, state elimination, regular and non-regular languages, closure properties, pigeonhole principle, pumping lemma, applications of pumping lemma, Myhill-Nerode method and decidability properties.

Unit III - Regular and Non-Regular Grammars

Formal grammars, context-free grammars, derivations, sentential forms, parse trees, ambiguity, regular grammars, conversion between finite automata and grammars, Chomsky hierarchy, simplification of CFGs, Chomsky Normal Form, Greibach Normal Form, Backus-Naur Form and CYK algorithm.

Unit IV - Pushdown Automata and Properties of Context-Free Languages

Pushdown automata, formal definition of NPDA, PDA design, deterministic pushdown automata, CFG to PDA and PDA to CFG conversions, two-stack PDA, pumping lemma for context-free languages, closure properties, decision problems and applications of PDA and CFLs.

Unit V - Turing Machines and Recursive Function Theory

Turing machine models, formal definitions, representations, construction techniques, modifications of Turing machines, universal Turing machines, linear bounded automata, Church-Turing thesis, recursive and recursively enumerable languages, halting problem, Post's Correspondence Problem, recursive function theory and computational complexity.

Why Use This Question Bank for AKTU Theory of Automata and Formal Languages?

It follows the AKTU syllabus unit by unit, so you can revise quickly, practise the types of questions asked in the semester examination and plan your preparation. Use it together with the related notes, previous year papers and syllabus for BCS402 available on Notes.UniversityAcademy.