TAFL PYQ 2018-19 AKTU Question Paper

AKTU · BTECH · Semester 4 · Theory of Automata and Formal Languages · Session 2018-19 · PYQ

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

  1. Q1a. For the given language L1 = ε, L2 = {a}, L3 = Ø. Compute L1 L2* U L3*. (2 marks, 2018-19)
  2. Q1b. Design a FA to accept the string that always ends with 101. (2 marks, 2018-19)
  3. Q1c. Write regular expression for set of all strings such that number of a's divisible by 3 over Σ = {a,b} (2 marks, 2018-19)
  4. Q1d. Construct the CFG for the Language L = {a2nbn |n>=3}. (2 marks, 2018-19)
  5. Q1e. What do you mean by ε-Closure in FA? (2 marks, 2018-19)
  6. Q1f. Explain Universal TM. (2 marks, 2018-19)
  7. Q1g. Explain Two Stack PDA. (2 marks, 2018-19)
  8. Q2a. Construct a minimum state DFA from given FA (Fig. 1) (7 marks, 2018-19)
  9. Q2b. Find the regular expression corresponding to the finite automata given below (Fig. 2) (7 marks, 2018-19)
  10. Q2c. Convert the following CFG to its equivalent GNF: S → AA | a, A → SS | b. (7 marks, 2018-19)
  11. Q2d. Design a PDA for the following language: L = {aⁱbʲcᵏ | i = j or j = k} (7 marks, 2018-19)
  12. Q2e. Design a TM for the following language: L = { aⁿ⁺²bⁿ | n > 0 } (7 marks, 2018-19)
  13. Q3a. Design FA for ternary number divisible by 5. (7 marks, 2018-19)
  14. Q3b. Explain Myhill-Nerode Theorem using suitable example. (7 marks, 2018-19)
  15. Q4a. Prove that the following Language L = {aⁿbⁿ} is not regular (7 marks, 2018-19)
  16. Q4b. Explain the Closure properties of regular expression. (7 marks, 2018-19)
  17. Q5a. Design the CFG for the following language: i) L = {0ᵐ1ⁿ | m ≠ n & m,n ≥ 1} ii) L = {aˡbᵐcⁿ | l + m = n & l,m ≥ 1} (7 marks, 2018-19)
  18. Q5b. Prove that the following Language L = {aⁿbⁿcⁿ} is not Context Free. (7 marks, 2018-19)
  19. Q6a. Design a PDA for the Language L = {WWᴿ | W={a,b}*} (7 marks, 2018-19)
  20. Q6b. Generate CFG for the given PDA M = ({q₀, q₁}, {0,1}, {x, z₀}, δ, q₀, z₀, q₁) where δ is given as: δ(q₀,1,z₀)=(q₀,xz₀), δ(q₀,1,x)=(q₀,xx), δ(q₀,0,x)=(q₀,x), δ(q₀,ε,x)=(q₁,ε), δ(q₁,ε,x)=(q₁,ε), δ(q₁,0,x)=(q₁,xx), δ(q₁,0,z₀)=(q₁,ε) (7 marks, 2018-19)
  21. Q7a. Design a TM for the following language: L = { aⁿbⁿcⁿ | n ≥ 1} (7 marks, 2018-19)
  22. Q7b. Write short note on: i) Recursive Language and Recursively Enumerable Language. ii) PCP problem and Modified PCP Problem (7 marks, 2018-19)

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