B.TechSemester 42025-26Theory Of Automata And Formal LanguagesBCS402
View PDFDownload

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.

Course:B.Tech
Semester:Semester 4
Session:2025-26
University:AKTU / UPTU

Rate this paper

Questions Asked in 2025-26

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

Section AAttempt all questions in brief. 2x7 = 14
  • a
    Define Deterministic Finite Automata (DFA)
  • b
    Design a DFA to accept all strings with abb as substring over alphabet {a,b}
  • c
    Find the shortest string not in the language of the regular expression a*(ba)*
  • d
    State the Pigeonhole Principle. ͪ ͧɮ
  • e
    Explain the difference between non-generating and unreachable symbols
  • f
    Define acceptance by final state and acceptance by empty stack in a PDA
  • g
    What is a Linear Bounded Automaton (LBA)
Section BAttempt any three of the following: 7 x 3 = 21
  • a
    Design a DFA which accepts set of strings such that every string containing 00 as substring but not 000 as a substring
  • b
    Using the pumping lemma, show that L = {anb2n| n ≥1} is not regular language
  • c
    Remove ε-productions from the given grammar
  • d
    Construct PDA that accepts L = { anb2n| n>=1}
  • e
    Define the Post Correspondence Problem (PCP). Why is it considered undecidable?
Section CAttempt any one part of the following: 7 x 1 = 7
  • a
    Define Non-Deterministic Finite Automata.Design a NFA to accepts strings over {0, 1}
    containing the substring 1101
  • b
    Define the Moore machine. Design a Moore machine to generate 1’s complement of given binary numbers
  • a
    Write 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}
  • b
    Construct regular expression for given DFA using Arden’s theorem
  • a
    Define Greibach Normal Form (GNF). Convert the following CFG into GNF
  • b
    What is ambiguity in a CFG?Construct a CFG for the language L = { aⁿbⁿ | n ≥ 0 }
  • a
    Design Two Stack Pushdown Automata for the given language
  • b
    Why are NPDAs considered more powerful than DPDAs? Provide an example of a language accepted by NPDA but not by DPDA
  • a
    What is a Universal Turing Machine (UTM)? How does it simulate other Turing Machines?
  • b
    Design a Turingmachine that accepts L={02n / n>=0}

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-22Theory Of Automata And Formal Languages2022-23Theory Of Automata And Formal Languages2023-24Theory Of Automata And Formal Languages2024-25

More B.Tech Semester 4 (2025-26) Papers

Other subjects from same semester and session

Technical Communication2025-26Mathematics Iii2025-26Mathematics Iv2025-26Mathematics V2025-26Cyber Security2025-26Python Programming2025-26Operating System2025-26Object Oriented Programming With Java2025-26
View all B.Tech Semester 4 2025-26 papers →

Syllabus & More PYQs

Paper solve karne se pehle unit-wise syllabus dekh lo

📘 Theory of Automata and Formal Languages — Unit-wise SyllabusBCS402AKTU 2nd Year SyllabusAKTU 2nd Year PYQs — All BranchesCSE 2nd Year Syllabus