B.TechSemester 42022-23Theory Of Automata And Formal LanguagesKCS-402
View PDFDownload

Theory Of Automata And Formal Languages (KCS-402) - AKTU Question Paper 2022-23

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 2022-23. 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:2022-23
University:AKTU / UPTU

Rate this paper

Questions Asked in 2022-23

Theory Of Automata And Formal Languages (KCS-402) — complete question paper

Section AAttempt all questions in brief. 2 x 10 = 20
  • a
    What do you understand by grammar?
  • b
    What do you mean by ε-Closure in FA?
  • c
    State Arden’s Theorem
  • d
    State Kleen’s Theorem
  • e
    Derive the CFG for (a+b)*
  • f
    Explain Chomsky Hierarchy
  • g
    Explain pumping lemma for context free language
  • h
    Draw the graphical representation for PDA. (i) Explain Halting Problem of Turing Machine. (j) Explain Linear bounded Automata
Section BAttempt any three of the following: 10x3=30
  • a
    Construct a DFA for ternary number divisible by 4
  • b
    Determine the FA accepted by the language described by the regular expression: (0+1)*0(0+1)*0(0+1)* over the alphabet {0,1} and al so mention the accepted language
  • c
    Consider the grammar with following production rules: S→ABD | AC A→aA | bAa |a B→bbA | aB | AB C→aCa |aD Convert the above grammar into Chomsky Normal Form
  • d
    Design a PDA for the language L= {WW T | W= (a+b) * }
  • e
    Write short notes on: i) Church’s Thesis ii) Recursive and Recursive Enumerable Language
Section CAttempt any one part of the following: 10x1=10
  • a
    Construct a DFA equivalent to the NFA
  • b
    Construct a minimum state automata equivalent to a DFA whose transition table is as follows where q3 and q4 are final state. State/  Input
  • a
    Find the regular expression corresponding to the finite automata given below
  • b
    State pumping lemma for regular language. Prove tha t the language L= {a p | p is prime} is not regular
  • a
    A context free grammar G is given by the following productions: Determine whether the grammar G is ambiguous or not .If ambiguous then construct an unambiguous grammar equivalent to G
  • b
    Explain Closure properties of regular language
  • a
    Design a two stack PDA for the language L={a n bncn | n>=1}
  • b
    Generate CFG for the given PDA M is defined as M = ({q0, q1}, {0,1} {x, z0}, δ, q0, z0, q1) where δ is given as follows: δ (q0,1, z0) =
  • b
    Write short notes on: (i) Variants of Turing Machine (ii) Post Correspondence problem (iii) Universal Turing Machine
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 — KCS-402
Questions that appeared in more than one session, found by comparing 2 years of Theory Of Automata And Formal Languages papers (2021-22, 2022-23)
2x
Write short notes on: (i) Variants of Turing Machine (ii) Post Correspondence problem (iii) Universal Turing Machine
Appeared in: 2021-22 · 2022-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 Languages2023-24Theory Of Automata And Formal Languages2024-25Theory Of Automata And Formal Languages2025-26
More B.Tech Semester 4 (2022-23) Papers
Other subjects from same semester and session
Mathematics V2022-23Introduction To Soft Computing2022-23Networks Analysis Synthesis2022-23Engineering Mathematics Iv2022-23Technical Communication2022-23Microprocessor2022-23Material Testing And Construction Practices2022-23Energy Science And Engineering2022-23
View all B.Tech Semester 4 2022-23 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