Theory Of Automata And Formal Languages (BCS402) - AKTU Question Paper 2025-26
B.Tech · Semester 4 · Free PDF Download
This is the official AKTU Theory Of Automata And Formal Languages Previous Year Question Paper for B.Tech Semester 4, academic session 2025-26. Published by Dr. A.P.J. Abdul Kalam Technical University (AKTU/UPTU), Lucknow. Free PDF download — no login required.
Rate this paper
Questions Asked in 2025-26
Theory Of Automata And Formal Languages (BCS402) — complete question paper · 70 marks · 3 Hours
- aDefine Deterministic Finite Automata (DFA)
- bDesign a DFA to accept all strings with abb as substring over alphabet {a,b}
- cFind the shortest string not in the language of the regular expression a*(ba)*
- dState the Pigeonhole Principle. ͪ ͧɮ
- eExplain the difference between non-generating and unreachable symbols
- fDefine acceptance by final state and acceptance by empty stack in a PDA
- gWhat is a Linear Bounded Automaton (LBA)
- aDesign a DFA which accepts set of strings such that every string containing 00 as substring but not 000 as a substring
- bUsing the pumping lemma, show that L = {anb2n| n ≥1} is not regular language
- cRemove ε-productions from the given grammar
- dConstruct PDA that accepts L = { anb2n| n>=1}
- eDefine the Post Correspondence Problem (PCP). Why is it considered undecidable?
- aDefine Non-Deterministic Finite Automata.Design a NFA to accepts strings over {0, 1}
containing the substring 1101
- bDefine the Moore machine. Design a Moore machine to generate 1’s complement of given binary numbers
- aWrite the regular expression for the languages: i) Accepting all the string containing any number of 0's and 1's over the set ∑ = {0, 1}. ii) Accepting all the string starting with 10101 over alphabet {0, 1}
- bConstruct regular expression for given DFA using Arden’s theorem
- aDefine Greibach Normal Form (GNF). Convert the following CFG into GNF
- bWhat is ambiguity in a CFG?Construct a CFG for the language L = { aⁿbⁿ | n ≥ 0 }
- aDesign Two Stack Pushdown Automata for the given language
- bWhy are NPDAs considered more powerful than DPDAs? Provide an example of a language accepted by NPDA but not by DPDA
- aWhat is a Universal Turing Machine (UTM)? How does it simulate other Turing Machines?
- bDesign a Turingmachine that accepts L={02n / n>=0}
Question text is extracted from the official AKTU question paper PDF above. Hindi translations are omitted — every question is printed in English in the original paper. Last verified: 2026-08-23.
Repeated Questions — BCS402
Questions that appeared in more than one session, found by comparing 3 years of Theory Of Automata And Formal Languages papers (2023-24, 2024-25, 2025-26)
Using the pumping lemma, show that L = {anb2n| n ≥1} is not regular language
Appeared in: 2024-25 · 2025-26
What is ambiguity in a CFG?Construct a CFG for the language L = { aⁿbⁿ | n ≥ 0 }
Appeared in: 2024-25 · 2025-26
Design a Turingmachine that accepts L={02n / n>=0}
Appeared in: 2024-25 · 2025-26
Theory Of Automata And Formal Languages — Other Year Papers
AKTU Theory Of Automata And Formal Languages PYQs from other sessions
More B.Tech Semester 4 (2025-26) Papers
Other subjects from same semester and session
Syllabus & More PYQs
Paper solve karne se pehle unit-wise syllabus dekh lo