Biju Patnaik University of Technology 2007 B.Tech Computer Science and Engineering FIFTH SEMESTER - AUTOMATA THEORY - Question Paper

FIFTH SEMESTER exam -2007

AUTOMATA THEORY

ans ques. no one which is compulsory and any 5 from the rest

1. ans the subsequent ques. : 2x10
a. provided an alphabet ? , what do you mean by a language L over ? ?
b. Devise a DFA which accept all strings ending with one .(Assume that ? ={0, 1})
c. describe a NFA.
d. You have DFA M¬1 which accept a language L¬1 and a different DFA M2 which accept the language L¬2 Devise a which accept the language L1 U L2
e. obtain the -clousre of the state {q0 } from the subsequent diagram :
f. describe a pushdown automaton.
g. obtain the language generated by the subsequent context-free grammer :
a S a | b S b |a | b
h. When is a situation – free grammer stated to be ambiguous?
i. when is a language L stated to be Turning recognizable ?Turning decidable?
j. Let f, g, h, k : N N. show that if f= O(h) and g= O(k) , then fg =O(hk).

2.a. Device a DFA which accept all binary string which are divisible by 4. 5
b. Convert the subsequent NFA to its equivalent DFA.

one 0,1 0,1

0,1





3. a. From the diagram of a DFA provided below, device a regular grammer which generates the language of the DFA. 4
0
1
1 0


0 1

b. define the regular expression corresponding to the language generated by the DFA in 3(a) above 3.
c. obtain the language generated by the subsequent DFA’s 3

0
e

i.


e 1






ii.






iii. a,b



4. a. State and prove the pumping lemma for regular language. 5
b. Use the pumping lemma to show that the language L={0n1n :n=1} in not regular. 5
5. a. State and prove the pumping lemma for context-free languages. 5
b. Show that the language L= {ancbn : n=1} is acceptable by a PDA. 5

6. a. describe a Turing machine. 5
b. Device a Turing machine which on a provided pair of positive integer (m,n) as input, will produce m+n output.[Assume that the positve integer are represented by a unary alphabet{1}] five
Therefore the input on the tape is :


0 one one …………… one one 0 one one ………………. one one 0

m 1’s n 1’s

The output should be


0 one one ……………….. one one 0

m+n 1’s
0= blank symbol.

7. a. Show that the set of all Turing recognizable languages is countable. 5
b. Show that if a language L is decidable so is its complement. 5
8. a. When is a function f : ? * ? * stated to be computable ? (Where ? is a provided alphabet) 2
b. When is a language A stated to be mapping reducible to a different language B (both over the identical alphabet)? 2
c. describe the class NP . define 3 issues belonging to the class NP. 6

Earning:   Approval pending.