B.TechSemester 42021-22Theory Of Automata And Formal LanguagesKCS402
View PDFDownload

Theory Of Automata And Formal Languages (KCS402) - AKTU Question Paper 2021-22

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 2021-22. 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:2021-22
University:AKTU / UPTU

Rate this paper

Questions Asked in 2021-22

Theory Of Automata And Formal Languages (KCS402) — complete question paper

Section AAttempt all q u e s t i o n s i n b r i e f . 2x10 = 20
  • a
    Define Alphabet and Str ing in Automata Theory. 2 2
  • b
    Give the definition of Determi nistic Finite Automaton (DFA). 2 1
  • c
    Explain in brief about the Kleen’s Theorem. 2 2
  • d
    Define Context Free Grammar (CFG). 2 1
  • e
    Write the Context Free Gramma r (CFG) for regular expression (0+1)* 2 3
  • f
    What are Right Linear gramma r and Left Linear grammars? 2 3
  • g
    Discuss briefly about the P ush Down Automata (PDA). 2 4
  • h
    What do you mean by Two stack Pushdown Automata? 2 4 (i) What do you mean by basic Turing Machine Model? 2 5 (j) What do you understand by the Halting Problem? 2 5
Section BAttempt any three o f t h e f o l l o w i n g : 10x3 = 30
  • a
    Explain in detail about the T uring Church’s Thesis and Recursively Enumerable languages
  • b
    Prove that the Compliment, Homomorphism, Inverse Homomorphi sm, and Closure of a Regular Language is also Regular
  • c
    Give the Complete descrip tion about the Chomsky Hierarchy. 10 3
  • d
    Convert the grammar S  aAA, A  a |aS| bS to a PDA that accepts the same language by Empty stack
  • e
    Grammar G is given with the production S->aSS A->b. Compute the string w= aababbb with the Left most and Right most derivation Tree
Section CAttempt any one p a r t o f t h e f o l l o w i n g : 10x1 = 10
  • a
    Write short notes on following. i) Turing Machine as Computer of Integer Functions ii) Universal Turing machine
  • b
    Explain in detail about the Pumping Lemma and application o f Pumping Lemma for Regular Languages
  • a
    Construct a Non Deterministic Finite Automation (NFA) for t he language L which accepts all the strings in which the third sym bol from right end is always 'a' over  = {a, b}
  • b
    Explain in detail about the Myhill-Nerode theorem using sui table example
  • a
    Prove that the following Language L = {a nbn: n>=0} is not a regular language
  • b
    Design a Turing Machine fo r the language L. Where, L={anbncn| n≥1} 10 5
  • a
    Prove that the Compliment, H omomorphism, Closure and Inverse Homomorphism of a Regular language is also Regular
  • b
    Minimize the given DFA shown below (Figure A). Figure A
  • a
    Explain in detail about the following. i) Closure properties of Regular Languages ii) Decidability- Decision properties of Regular Languages
  • b
    Check whether the grammar is ambiguous or not. R-> R+R/ RR/ R*/ a / b / c. Obtain the string w = a+b*c

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.

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

More B.Tech Semester 4 (2021-22) Papers

Other subjects from same semester and session

Communication Engineering2021-22Manufacturing Processes2021-22Networks Analysis Synthesis2021-22Basic Data Structure And Algorithms2021-22Operating Systems2021-22Technical Communication2021-22Material Science2021-22Maths Iv2021-22
View all B.Tech Semester 4 2021-22 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