TAFL PYQ 2017-18 AKTU Question Paper

AKTU · BTECH · Semester 4 · Theory of Automata and Formal Languages · Session 2017-18 · PYQ

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

  1. Q1a. Define alphabet, string and language. (2 marks, 2017-18)
  2. Q1b. Design a regular expression that accepts all the strings for input alphabet {a,b} containing exactly 2 a's. (2 marks, 2017-18)
  3. Q1c. Design a NFA that accepts all the strings for input alphabet {a,b} containing the substring abba. (2 marks, 2017-18)
  4. Q1d. Define Chomsky hierarchy. (2 marks, 2017-18)
  5. Q1e. Is context free language closed under union? If yes, give an example. (2 marks, 2017-18)
  6. Q1f. Convert NFA into equivalent DFA by taking any suitable example. (2 marks, 2017-18)
  7. Q1g. Remove useless productions from the given productions: SAB|ab, AaA|B|a, BD|E (2 marks, 2017-18)
  8. Q2a. Define Deterministic Finite Automata (DFA) and design a DFA that accepts the binary number whose equivalent is divisible by 5. (7 marks, 2017-18)
  9. Q2b. State recursive definition of regular expression and construct a regular expression corresponding to the state transition diagram as shown in Fig.1 (7 marks, 2017-18)
  10. Q2c. Reduce the given grammar G=({S,A,B},{a,b},P,S) to Chomsky Normal Form. Where P is defined as: S→ bA | aB, A→ bAA | aS | a, B → aBB | bS | b (7 marks, 2017-18)
  11. Q2d. What is Push Down Automata (PDA)? Design the PDA for the language L = {wcwR|w∈{a,b}*} (7 marks, 2017-18)
  12. Q2e. Define Turing Machine (TM). Construct the TM for the language L = {anbn|n>0}. (7 marks, 2017-18)
  13. Q3a. Describe Mealy and Moore machines with example. Convert the given Mealy machine as shown in Fig. 2 into Moore Machine. (7 marks, 2017-18)
  14. Q3b. Construct the minimum state automata equivalent to DFA described by Fig. 3 (7 marks, 2017-18)
  15. Q4a. State Pumping Lemma for regular sets. Show that the set L={a^p | p is a prime} is not regular. (7 marks, 2017-18)
  16. Q4b. Discuss closure properties i.e. concatenation, union, intersection, complement of regular languages. (7 marks, 2017-18)
  17. Q5a. Discuss inherent ambiguity of context free languages with suitable example. Construct the context free grammar that accepts language L={a^i b^j c^k | i = j or j = k; i, j, k are positive integers}. (7 marks, 2017-18)
  18. Q5b. Define parse tree. Find parse tree for the string abbcde considering the productions- S→aAcBe, A→Ab, A→b, B→d. Is this ambiguous? Justify. (7 marks, 2017-18)
  19. Q6a. Differentiate between deterministic PDA (DPDA) and non-deterministic PDA (NPDA) with suitable example. Also discuss two stack PDA with example. (7 marks, 2017-18)
  20. Q6b. Construct a PDA equivalent to the following CFG productions: S→aAA, A→aS | bS | a (7 marks, 2017-18)
  21. Q7a. Write short notes on the following: (i) Halting problem of Turing machine (ii) Recursive Language (iii) Variants of Turing Machine (7 marks, 2017-18)
  22. Q7b. Define Post's Correspondence Problem (PCP) and Modified PCP with its applications. Find any three PCP solutions of the lists x=(b,bab3,ba) and y=(b3,ba,a). (7 marks, 2017-18)

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