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) — complete question paper · 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. 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 CFG for the language L = {aⁿbⁿ | n ≥ 0}

Appeared in: 2024-25 · 2025-26

Design a Turing Machine to accept the language L = {aⁿbⁿ | n ≥ 1}

Appeared in: 2024-25 · 2025-26

Construct a DFA corresponding to the following NFA

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

Using Pumping Lemma, show that the language L = {aⁿbⁿcⁿ | n ≥ 0} is not regular

Appeared in: 2024-25 · 2025-26