Theory of Computation 2072

Attempt all the questions.

                                                                Group A                                                         (8x4=32)

1.  Define the term: Kleene closure, union, concatenation and power of an alphabet with example.

2.  Construct a DFA that accepts only the strings ab, abb and baa not more from {a, b}^*.

3.  Find the regular expression corresponding to the following languages over {0, 1}^*.

a)       The language of all strings containing exactly two 0's.

b)       The language of all strings containing 00 or 101 as substrings.

4.  Construct the FA recognizing the language corresponding to the following regular expressions.

a) (11 + 10)^*01

b) (111 + 100)*10

5.  State the pumping lemma for regular language. Show by example, how can you use it to prove that a language is not regular.

6.  Explain the method to convert a given CFG into equivalent PDA.

7.  What do you mean by problem reduction? Also explain about NP-Completeness.

8.  What is the role of a Turing machine? Explain.

                                                                Group B                                                         (6x8=48)

9.  What is finite automata? Describe its different variations with suitable examples.

10.  Describe the method of subset construction to convert a given NFA into equivalent DFA with suitable example.

11.  Give the formal definition of Push Down Automata. Construct a PDA accepting the language

L = {0ⁿ1ⁿ | n > 0}

12.  Given the following grammar,

S → AAC |

A → aAb | ab | ɛ

C → aC | a | ɛ

Simplify the grammar and convert it into equivalent grammar in CNF.

13.  Define Turing Machine. Construct the Turing machine that accepts the languages

                L={aⁿbⁿ | n>=0}

14.  Write short notes on (Any two):

a)       Unrestricted Grammar

b)       Universal Turing Machine

c)       CNF-SAT problem Complexity