B.Tech II Year II Semester Examinations, May - 2019

FORMAL LANGUAGES AND AUTOMATA THEORY

(Common to CSE, IT)

Time: 3 hours

Max. Marks: 75

Note: This question paper contains two parts A and B.

--- Content provided by FirstRanker.com ---

Part A is compulsory which carries 25 marks. Answer all questions in Part A.

Part B consists of 5 Units. Answer any one full question from each unit. Each question carries 10 marks.

Part A (25 Marks)

1. 1. Define DFA. Give an example. (2M)
   2. Write regular expression for set of all strings over {a,b} containing "abb" as a substring. (3M)
   3. Write a context free grammar for the language L = {aⁿbⁿ | n ≥ 1}. (2M)

   --- Content provided by FirstRanker.com ---

   4. Define Instantaneous description of a PDA. (3M)
   5. When is a Turing Machine said to be decidable? (2M)
   6. State pumping lemma for regular sets. (3M)
   7. What are useless symbols in a grammar? (2M)
   8. What is Greibach Normal Form (GNF)? (3M)

   --- Content provided by FirstRanker.com ---

   9. Define Multi-Tape Turing Machine. (2M)
   10. Define Post Correspondence Problem. (3M)

Part B (50 Marks)

(Answer any one full question from each unit)

Unit - I

1. 2.a) Design a DFA which accepts set of all strings over the alphabet {0, 1} that when interpreted as a binary number is divisible by 5. (5M)

   --- Content provided by FirstRanker.com ---

   b) Construct a minimum state DFA equivalent to the DFA given below: (5M)

   Note: Replace 'https://www.firstranker.com/sample_image.png' with the actual image URL if available.

   OR

   3.a) Construct a NFA without ε - transitions equivalent to the NFA with ε - transitions given below: (5M)

   Note: Replace 'https://www.firstranker.com/sample_image2.png' with the actual image URL if available.

   b) Convert the following regular expression to an NFA with ε-transitions: (5M)

   (a/b)*abb

   --- Content provided by FirstRanker.com ---

Unit - II

1. 4.a) State and prove pumping lemma for regular sets. (5M)

   b) Show that L = {0ⁿ1ⁿ | n ≥ 1} is not regular. (5M)

   OR

   5.a) Prove that regular sets are closed under complement, intersection, union and reversal. (5M)

   --- Content provided by FirstRanker.com ---

   b) Minimize the following finite automaton using Myhill-Nerode Theorem. (5M)

   Note: Replace 'https://www.firstranker.com/sample_image3.png' with the actual image URL if available.

Unit - III

1. 6.a) Convert the following grammar to Chomsky Normal Form (CNF). (5M)

   S → aA | bB | a | b

   A → aSa | a

   --- Content provided by FirstRanker.com ---

   B → bSb | b

   b) Design a PDA for the language L = {aⁿbⁿ | n ≥ 1}. (5M)

   OR

   7.a) Design a PDA for the language L = {wcw^R | w ∈ (a+b)*}. (5M)

   b) Explain different types of acceptance of a PDA. (5M)

   --- Content provided by FirstRanker.com ---

Unit - IV

1. 8.a) Design a Turing Machine to accept the language L = {aⁿbⁿcⁿ | n ≥ 1}. (5M)

   b) Explain the different types of Turing Machines. (5M)

   OR

   9.a) Design a Turing Machine to accept the language L = {ww^R | w ∈ (a+b)*}. (5M)

   --- Content provided by FirstRanker.com ---

   b) Write short notes on Universal Turing Machine. (5M)

Unit - V

1. 10.a) Define decidability and undecidability. Give an example of undecidable problem. (5M)

   b) State and prove post correspondence problem. (5M)

   OR

   --- Content provided by FirstRanker.com ---

   11.a) Show that halting problem of a Turing Machine is undecidable. (5M)

   b) Write short notes on Modified PCP. (5M)

--o00o--

Get more at: FirstRanker.com

--- Content provided by FirstRanker.com ---