TAFL PYQ 2023-24 AKTU Question Paper

AKTU · BTECH · Semester 4 · Theory of Automata and Formal Languages · Session 2023-24 · PYQ

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

  1. Q1a. Give the mathematical definition of DFA. Differentiate between NFA and DFA. (2 marks, 2023-24)
  2. Q1b. Construct Deterministic Finite Automata (DFA) to accept string that always ends with 101 over alphabet Σ ={0,1} (2 marks, 2023-24)
  3. Q1c. Give regular expressions that represent the language (L), which has all binary strings having two consecutive 0s and two consecutive 1s over the alphabet Σ = {0, 1}. (2 marks, 2023-24)
  4. Q1d. Compute the Language generated by the given CFG G = ({S}, {a, b}, P, S} where P is defined by: {S → SS, S → ab, S → ba, S → ε} (2 marks, 2023-24)
  5. Q1e. Let G be the grammar S → 0B | 1A, A → 0 | 0S | 1AA, B → 1 | 1S | 0BB. Determine the leftmost derivation for the string 00110101 (2 marks, 2023-24)
  6. Q1f. Explain the concept of two stack PDA. Give an example of a language that is accepted by two stack PDA but not accepted by normal one stack PDA. (2 marks, 2023-24)
  7. Q1g. Explain Multi Tape Turing Machine. (2 marks, 2023-24)
  8. Q2a. Construct a Finite automata (DFA) which accepts all binary numbers whose decimal equivalent is divisible by 4 over Σ = {0, 1}. (7 marks, 2023-24)
  9. Q2b. Compute the regular expression using Arden's Theorem for the following DFA. (7 marks, 2023-24)
  10. Q2c. Write an equivalent left linear grammar from the given right linear grammar. S → 0A | 1B, A → 0C | 1A | 0, B → 1B | 1A | 1, C → 0 | 0A (7 marks, 2023-24)
  11. Q2d. Differentiate between DPDA and NPDA. Construct a PDA that accepts language L = {aⁿbⁿ | n ≥ 1}. (7 marks, 2023-24)
  12. Q2e. Differentiate between Deterministic Turing machine and Non-Deterministic Turing machine. Design a Turing machine for the language L={ww | w ε (a + b)*}. (7 marks, 2023-24)
  13. Q3a. Construct a DFA corresponding to the following NFA with ε moves: (7 marks, 2023-24)
  14. Q3b. Express in the minimum state automata equivalent to DFA described in below figure: (7 marks, 2023-24)
  15. Q4a. State Pumping Lemma for Regular Language. Show that the given language L={ap | Where p is a prime} is not regular. (7 marks, 2023-24)
  16. Q4b. Discuss closure properties (i.e. union, concatenation, complement, intersection and difference) of regular language. (7 marks, 2023-24)
  17. Q5a. Reduce the given grammar G = ({S, A, B}, {a, b}, P, S) to Chomsky Normal form. Where P is defined by: S → bA | aB, A → bAA | aS | a, B → aBB | bS | b (7 marks, 2023-24)
  18. Q5b. Design a CFG for the following language: (i) L= {0m 1n | m ≠ n & m, n >= 1} (ii) L= {ap bq cr | p + q = r & p, q >= 1} (7 marks, 2023-24)
  19. Q6a. Construct PDA equivalent to the following CFG G = ({S, A}, {0,1}, P, S} where P is defined by: S → 0S1 | A, A → 1A0 | S | ε (7 marks, 2023-24)
  20. Q6b. Find the equivalent CFG of the following PDA P = ({q0, q1}, {a, b}, {a, z0}, δ, q0, z0) where δ is given by: δ(q0,a,z0)=(q0,az0), δ(q0,a,a)=(q1,aa), δ(q1,a,a)=(q1,ε), δ(q1,ε,z0)=(q1,ε) (7 marks, 2023-24)
  21. Q7a. Construct Turing Machine that accepts language L={a²ⁿbⁿ | n>=1}. Also show the instantaneous description for the string w = aaaabb. (7 marks, 2023-24)
  22. Q7b. Explain the any two of the following: i. Universal Turing Machine. ii. Post Correspondence Problem. iii. Recursive and recursively Enumerable Languages (7 marks, 2023-24)

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