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.

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

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

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 Deterministic Finite Automaton (DFA). [2M]
   2. Write a regular expression to denote a language L which accepts all strings which begin or end with 00. [3M]
   3. Define Context Free Grammar (CFG). [2M]
   4. Give an example of ambiguous grammar. [3M]

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

   5. Define Pushdown Automata (PDA). [2M]
   6. State pumping lemma for context free languages. [3M]
   7. What are the different types of Turing Machines? [2M]
   8. What are recursively enumerable languages? [3M]
   9. Define undecidable problem. [2M]

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

   10. What is Post Correspondence Problem (PCP)? [3M]

PART - B (50 Marks)

(Answer any one full question from each unit. Each question carries 10 marks)

UNIT - I

1. 2. a) Construct a DFA equivalent to the regular expression (ab+baa)*. [5M] b) Explain about equivalence between two finite automata. [5M]

   OR

   3. a) Construct a NFA for the regular expression a*b+b*a. [5M] b) Explain the procedure for converting NFA to DFA. [5M]

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

UNIT - II

1. 4. a) Convert the following grammar to Chomsky Normal Form (CNF). [5M] S ? aABB | aAA A ? aBB | a B ? bBB | A b) Explain about closure properties of context free languages. [5M]

   OR

   5. a) Define Greibach Normal Form (GNF). Convert the following grammar to GNF. [5M] S ? AA | b A ? SS | a b) Construct a derivation tree for the string "aabbab" using the grammar S ? aAS | a | bSS | b. [5M]

UNIT - III

1. 6. Design a PDA for recognizing L = {0ⁿ1ⁿ | n = 1}. [10M]

   OR

   7. Convert the following grammar to PDA. [10M] S ? aABB | aAA A ? aBB | a B ? bBB | A

UNIT - IV

1. 8. Explain the different types of Turing machine with neat diagrams. [10M]

   OR

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

   9. Design a Turing machine to accept the language L = {0ⁿ1ⁿ2ⁿ | n = 1}. [10M]

UNIT - V

1. 10. Explain about decidability and undecidability problems. [10M]

   OR

2. 11. Write short notes on: [10M] a) Classes of P and NP b) NP-Completeness.

---ooOoo---

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

Get more study materials at FirstRanker.com