## Automata Theory - May 2016

### Information Technology (Semester 4)

TOTAL MARKS: 80

TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.

(2) Attempt any **three** from the remaining questions.

(3) Assume data if required.

(4) Figures to the right indicate full marks.

### IT

**1(a)** What is the complement of the language accepted by the NFA shown below? Assume S={a} and c is the empty string.

**1(b)**Definition of a language L with alphabet {a} is given as following

{ a

^{n k}| k > 0, and n is a positive integer constant }

What is the minimum number of states needed in a DFA to recognize L?(2 marks)

**1(c)**What is Multi-Tape Turing Machine?(3 marks)

**1(d)**Design Mealy Machine to convert each occurrence of substring 1000 by 1001.(7 marks)

**1(e)**State that whether a following Language is Regular or not.

1) L = {WW

^{R}| |W|=2 over ∑={a,b}}

2) L = {WW

^{R}| Wc (a,b)*}(6 marks)

**2(a)**Give formal definition of a Turing Machine.(5 marks)

**2(b)**Write a regular expression for the following languages, over sigma=(a,b}.

1. Seventh symbol from right must be a.

2. Every second character is b.

3. Exactly one ab.(10 marks)

**2(c)**Explain Chomsky Hierarchy.(5 marks)

**3(a)**Construct a TM for accepting Even palindromes.(10 marks)

**3(b)**Design PDA For recognizing L={a

^{n}b

^{2 n+1}| n>=1}(10 marks)

**4(a)**Convert the following grammar to Chomsky Normal Form. Show all the relevant steps briefly.

S --->bA | aB

A --->bAA | aS | a

B ---> aBB | bS | b(10 marks)

**4(b)**Give the technical strategy to convert CFG to GNF.

Convert the following grammar to GNF.

S → AA | a

A → SS | b(10 marks)

**5(a)**Enumerate the differences between finite automata and non-deterministic automata?(8 marks)

**5(b)**Construct NFA, DFA for the regular Expression R=ab(a+b)+abb. Obtain minimized DFA.(7 marks)

**5(c)**Give formal definition of a Push Down Automata(PDA).(5 marks)

### Write short note on

**6(a)** Unsolvable problems(10 marks)
**6(b)** Recursive and Recursively enumerable languages.(10 marks)
**6(c)** Simplification of CFG.(10 marks)