TAFL PYQ 2021-22 AKTU Question Paper

AKTU · BTECH · Semester 4 · Theory of Automata and Formal Languages · Session 2021-22 · PYQ

AKTU Theory of Automata and Formal Languages previous year question paper 2021-22 for B.Tech Semester 4. Covers Basic Concepts and Automata Theory, Regular…

Open the interactive reader to study this resource on AcademicArk.

Theory of Automata and Formal Languages AKTU syllabus

  1. Unit 1: Basic Concepts and Automata Theory
  2. Unit 2: Regular Expressions and Languages
  3. Unit 3: Regular and Non-Regular Grammars
  4. Unit 4: Push Down Automata and Properties of Context Free Languages
  5. Unit 5: Turing Machines and Recursive Function Theory

Questions in Theory of Automata and Formal Languages AKTU PYQ 2021-22

  1. Q1a. Define Alphabet and String in Automata Theory. (2 marks, 2021-22)
  2. Q1b. Give the definition of Deterministic Finite Automaton (DFA). (2 marks, 2021-22)
  3. Q1c. Explain in brief about the Kleen's Theorem. (2 marks, 2021-22)
  4. Q1d. Define Context Free Grammar (CFG). (2 marks, 2021-22)
  5. Q1e. Write the Context Free Grammar (CFG) for regular expression (0+1)* (2 marks, 2021-22)
  6. Q1f. What are Right Linear grammar and Left Linear grammars? (2 marks, 2021-22)
  7. Q1g. Discuss briefly about the Push Down Automata (PDA). (2 marks, 2021-22)
  8. Q1h. What do you mean by Two stack Pushdown Automata? (2 marks, 2021-22)
  9. Q1i. What do you mean by basic Turing Machine Model? (2 marks, 2021-22)
  10. Q1j. What do you understand by the Halting Problem? (2 marks, 2021-22)
  11. Q2a. Explain in detail about the Turing Church's Thesis and Recursively Enumerable languages. (10 marks, 2021-22)
  12. Q2b. Prove that the Compliment, Homomorphism, Inverse Homomorphism, and Closure of a Regular Language is also Regular. (10 marks, 2021-22)
  13. Q2c. Give the Complete description about the Chomsky Hierarchy. (10 marks, 2021-22)
  14. Q2d. Convert the grammar S -> aAA, A -> a | aS | bS to a PDA that accepts the same language by Empty stack. (10 marks, 2021-22)
  15. Q2e. 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. (10 marks, 2021-22)
  16. Q3a. Write short notes on following. i) Turing Machine as Computer of Integer Functions ii) Universal Turing machine (10 marks, 2021-22)
  17. Q3b. Explain in detail about the Pumping Lemma and application of Pumping Lemma for Regular Languages. (10 marks, 2021-22)
  18. Q4a. Construct a Non Deterministic Finite Automation (NFA) for the language L which accepts all the strings in which the third symbol from right end is always 'a' over Σ = {a, b}. (10 marks, 2021-22)
  19. Q4b. Explain in detail about the Myhill-Nerode theorem using suitable example. (10 marks, 2021-22)
  20. Q5a. Prove that the following Language L = {aⁿbⁿ: n>=0} is not a regular language. (10 marks, 2021-22)
  21. Q5b. Design a Turing Machine for the language L. Where, L={aⁿbⁿcⁿ | n≥1} (10 marks, 2021-22)
  22. Q6a. Prove that the Compliment, Homomorphism, Closure and Inverse Homomorphism of a Regular language is also Regular. (10 marks, 2021-22)
  23. Q6b. Minimize the given DFA shown below (Figure A). (10 marks, 2021-22)
  24. Q7a. Explain in detail about the following. i) Closure properties of Regular Languages ii) Decidability- Decision properties of Regular Languages (10 marks, 2021-22)
  25. Q7b. Check whether the grammar is ambiguous or not. R-> R+R/ RR/ R*/ a / b / c. Obtain the string w = a+b*c (10 marks, 2021-22)

AKTU paper codes: BCS402, KCS402, RCS403

Theory of Automata and Formal Languages previous year papers

More Theory of Automata and Formal Languages resources

Browse all notes · Semester 4 notes