Theory Of Automata And Formal Languages (BCS402) - AKTU Question Paper 2023-24
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 2023-24. 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 2023-24
Theory Of Automata And Formal Languages (BCS402) — complete question paper · 70 marks · 3 Hours
- aGive the mathematical definition of DFA. Differentiate between N F A a n d DFA
- bConstruct Deterministic Finite Automata (DFA) to accept string that always
ends with 101 over alphabet Σ ={0,1} - cGive regular expressions that represent the language (L), whic h has all binary strings having two consecutive 0s and two consecutive 1s over the alphabet Σ
- dCompute the Language generated by the given CFG G = ({S}, {a, b}, P, S}
where P is defined by: {S → SS, S → ab, S → ba, S → ε} - eLet G be the grammar Determine the leftmost derivation for the string 00110101
- fExplain the concept of two stack PDA. Give an example of a lan guage that is accepted by two stack PDA but not accepted by normal one stack PDA
- gExplain Multi Tape Turing Machine
- aConstruct a Finite automata (DFA) which accepts all binary num bers whose decimal equivalent is divisible by 4 over Σ = {0, 1}
- bCompute the regular expression using Arden`s Theorem for the f ollowing DFA
- cWrite an equivalent left linear grammar from the given right linear grammar
- dDifferentiate between DPDA and NPDA. Construct a PDA that acce pts language L = {𝑎𝑏 | 𝑛 1}
- eDifferentiate between Deterministic Turing machine and Non-Det erministic Turing machine. Design a Turing machine for the language L={ww | w (a +
- aConstruct a DFA corresponding to the following NFA with 𝛜 moves
- bExpress in the minimum state automata equivalent to DFA described in below figure
- aState Pumping Lemma for Regular Language. Show that the given l anguage L={ap | Where p is a prime} is not regular
- bDiscuss closure properties (i.e. union, concatenation, complement, intersection and difference) of regular language
- aReduce the given grammar G = ({S, A, B}, {a, b}, P, S) to Choms ky Normal form. Where P is defined by: A bAA | aS | a B aBB | bS | b
- bDesign a CFG for the following language:
(i) L= {0m 1n | m ≠ n & m, n>=1} (ii) L= {ap bq cr | p + q = r & p, q > = 1} - aConstruct PDA equivalent to the following CFG G = ({S, A}, {0,1 }, P, S}
where P is defined by
- bFind the equivalent CFG of the following PDA P = ({q0, q1,}, {a, b}, {a, z0}, δ, q0, z0) where δ is given by
- aConstruct Turing Machine that accepts language L={ 𝑎ଶ𝑏 | n > = 1 } . A l s o show the instantaneous description for the string w = aaaabb
- bExplain the any two of the following: i. Universal Turing Machine. ii. Post Correspondence Problem. iii. Recursive and recursively Enumerable Languages
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)
Construct a DFA corresponding to the following NFA with 𝛜 moves
Appeared in: 2023-24 · 2024-25
Express in the minimum state automata equivalent to DFA described in below figure
Appeared in: 2023-24 · 2024-25
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 (2023-24) Papers
Other subjects from same semester and session
Syllabus & More PYQs
Paper solve karne se pehle unit-wise syllabus dekh lo