B.TechSemester 42024-25Theory Of Automata And Formal LanguagesBCS402

Theory Of Automata And Formal Languages (BCS402) - AKTU Question Paper 2024-25

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 2024-25. Published by Dr. A.P.J. Abdul Kalam Technical University (AKTU/UPTU), Lucknow. Free PDF download — no login required.

Course:B.Tech

Semester:Semester 4

Session:2024-25

University:AKTU / UPTU

Rate this paper

Questions Asked in 2024-25

Theory Of Automata And Formal Languages (BCS402) — extracted question text · 70 marks · 3 Hours

Section AAttempt all questions in brief. 02 x 7 = 14

a
Define the term “Alphabet” in the context of automata theory
b
Differentiate between DFA and NFA
c
Write the regular expression for the language containing strings over {0,1}
```
ending with 01
```
d
What is the ambiguity in Context-Free Grammars (CFGs)?
e
Construct a CFG for the language L = {aⁿbⁿ | n ≥ 0}
f
Find whether the following grammar is ambiguous or not: S → S*S | S+S | a
g
Design a Turing Machine to accept the language L = {aⁿbⁿ | n ≥ 1}

Section BAttempt any three of the following: 07 x 3 = 21

Prove that for every NFA, there exists an equivalent DFA. Show construction

using subset method for the given NFA:
States = {q0, q1}, Input = {0,1}, Start = q0, Final = {q1},
Transitions:
  δ(q0, 0) = {q0, q1}
  δ(q0, 1) = {q0}
  δ(q1, 1) = {q1}
States = {q0, q1}, Input = {0,1}, Start = q0, Final = {q1},
Transitions:   δ(q0, 0) = {q0, q1}
  δ(q0, 1) = {q0}
  δ(q1, 1) = {q1}

b
Prove using Arden’s Theorem the regular expression for the following transition diagram: States: A (start), B (final) Transitions: States: A (start), B (final) Transitions
c
Convert the following regular grammar to a Finite Automaton
d
Design a PDA that accepts the language L = {ww^R | w ∈ {a, b}*}
e
Design a Turing Machine to compute the function f(n) = n + 1 where n is a unary number (e.g., n=3 → “111”)

Section CAttempt any one part of the following: 07 x 1 = 07

a
Construct a DFA corresponding to the following NFA
b
Express in the minimum state automata equivalent to DFA described in below figure
a
Using Pumping Lemma, show that the language L = {aⁿbⁿcⁿ | n ≥ 0} is not regular
b
Prove that (a+b)*a(a+b)* is a regular language using Arden’s Theorem
a
Convert the following CFG into Chomsky Normal Form (CNF): S → aSB | ε S → aSB | ε
b
Prove using derivation trees whether the grammar: S → aSb | ε is ambiguous or not. Explain ambiguity
a
Simplify the following CFG: S → AbaC, A → BC, B → b | ε , C→D | ε , D→d S → AbaC, A → BC, B → b | ε , C→D | ε , D→d
b
Design a PDA to accept palindromes over {a, b}
a
Explain the concept of Universal Turing Machine. Construct a Turing Machine that computes f(n) = 2n for unary input
b
Discuss Post’s Correspondence Problem (PCP) with an example showing undecidability

Question text is extracted from the official AKTU question paper PDF above. Check the original PDF for equations, diagrams and complete wording. Extracted: 2026-08-23.

Theory Of Automata And Formal Languages — Other Year Papers

AKTU Theory Of Automata And Formal Languages PYQs from other sessions

Theory Of Automata And Formal Languages2021-22 Theory Of Automata And Formal Languages2022-23 Theory Of Automata And Formal Languages2023-24 Theory Of Automata And Formal Languages2025-26

More B.Tech Semester 4 (2024-25) Papers

Other subjects from same semester and session

Analog Circuits2024-25 Applied Thermodynamics2024-25 Polymer Science And Technology2024-25 Analog Electronics Circuits2024-25 Universal Human Values Professional Ethics2024-25 Basics Of Database Management Systems2024-25 Python Programming2024-25 Digital Electronics2024-25

View all B.Tech Semester 4 2024-25 papers →

Syllabus & More PYQs

Paper solve karne se pehle unit-wise syllabus dekh lo

📘 Theory of Automata and Formal Languages — Unit-wise SyllabusBCS402 AKTU 2nd Year Syllabus AKTU 2nd Year PYQs — All Branches CSE 2nd Year Syllabus