TAFL PYQ 2022-23 AKTU Question Paper

AKTU · BTECH · Semester 4 · Theory of Automata and Formal Languages · Session 2022-23 · PYQ

AKTU Theory of Automata and Formal Languages previous year question paper 2022-23 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 2022-23

  1. Q1a. What do you understand by grammar? (2 marks, 2022-23)
  2. Q1b. What do you mean by ε-Closure in FA? (2 marks, 2022-23)
  3. Q1c. State Arden's Theorem. (2 marks, 2022-23)
  4. Q1d. State Kleen's Theorem. (2 marks, 2022-23)
  5. Q1e. Derive the CFG for (a+b)*. (2 marks, 2022-23)
  6. Q1f. Explain Chomsky Hierarchy. (2 marks, 2022-23)
  7. Q1g. Explain pumping lemma for context free language. (2 marks, 2022-23)
  8. Q1h. Draw the graphical representation for PDA. (2 marks, 2022-23)
  9. Q1i. Explain Halting Problem of Turing Machine. (2 marks, 2022-23)
  10. Q1j. Explain Linear bounded Automata. (2 marks, 2022-23)
  11. Q2a. Construct a DFA for ternary number divisible by 4. (10 marks, 2022-23)
  12. Q2b. 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 also mention the accepted language? (10 marks, 2022-23)
  13. Q2c. Consider the grammar with following production rules: S→ABD | AC, A→aA | bAa | a, B→bbA | aB | AB, C→aCa | aD, D→aD | bC. Convert the above grammar into Chomsky Normal Form. (10 marks, 2022-23)
  14. Q2d. Design a PDA for the language L= {WW^T | W= (a+b)*} (10 marks, 2022-23)
  15. Q2e. Write short notes on: i) Church's Thesis ii) Recursive and Recursive Enumerable Language (10 marks, 2022-23)
  16. Q3a. Construct a DFA equivalent to the NFA (10 marks, 2022-23)
  17. Q3b. Construct a minimum state automata equivalent to a DFA whose transition table is as follows where q3 and q4 are final state. (transition table with states Q0-Q7 over inputs a,b given) (10 marks, 2022-23)
  18. Q4a. Find the regular expression corresponding to the finite automata given below: (10 marks, 2022-23)
  19. Q4b. State pumping lemma for regular language. Prove that the language L= {a^p | p is prime} is not regular. (10 marks, 2022-23)
  20. Q5a. A context free grammar G is given by the following productions: E→E+E|E-E|E*E|E^E|N, N→0|1|2|3|4|5|6|7|8|9. Determine whether the grammar G is ambiguous or not. If ambiguous then construct an unambiguous grammar equivalent to G. (10 marks, 2022-23)
  21. Q5b. Explain Closure properties of regular language. (10 marks, 2022-23)
  22. Q6a. Design a two stack PDA for the language L={a^n b^n c^n | n>=1} (10 marks, 2022-23)
  23. Q6b. Generate CFG for the given PDA M = ({q0, q1}, {0,1}, {x, z0}, δ, q0, z0, q1) where δ is given as: δ(q0,1,z0)=(q0,xz0), δ(q0,1,x)=(q0,xx), δ(q0,0,x)=(q0,x), δ(q0,ε,x)=(q1,ε), δ(q1,ε,x)=(q1,ε), δ(q1,0,x)=(q1,xx), δ(q1,0,z0)=(q1,ε) (10 marks, 2022-23)
  24. Q7a. Design a Turing Machine for the language: L={a^n b^n c^n | n>=1} (10 marks, 2022-23)
  25. Q7b. Write short notes on: (i) Variants of Turing Machine (ii) Post Correspondence problem (iii) Universal Turing Machine (10 marks, 2022-23)

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