Osmania University (OU) 2009 B.E Computer Science ALC - Question Paper

B.E. 3/4 CSE two SEM MAIN examination APRIL/MAY-2009
AUTOMATA LANGUAGES AND calculation

PART-A
1.Define 2 way finite automata (2 marks)
2.what is satisfiability?(2m)
3.prove whether (0+1)*110 is regular or not?(3m)
4.define ambiguity. is the provided grammer ambiguous?(3m)
s->s/s
s->a
5.what is GNF?(2m)
6.eliminate unit production.(3m)
S->AB
A->a
B->C/b
C->D
D->E
E->a
7.explain transition function in Turing machine?(3m)
8.state any two closure properties of CFL.(3m)
9.what is REL?(2m)
10.define LR(0) grammer?(2m)

PART-B
11. a) state and prove Myhill nerode therem?(5m)
b)construct DFA.5m)
0 1
->A {A,B} {A}
B _ {C}
C _ {D}
*D {D} {D}
12. a)convert the provided grammer into CNF. (5m)
S->aSb/aA/dB/a/b
A->aA/a
B->bB/b
b)state any closure propeties of CFL.(5m)
13. a)write a short note on Universal Turing machine.(5m)
b)Design a turing machine.(5m)
L={wwR/w is in (0+1)*}
14.design a PDA {0(power n)1(power m)0(power n)/m,n>=1}.(10m)
15.show the PCP with 2 lists X=(b,babbb,ba), Y=(bbb,ba,a) has a solution. provide the solution sequence.(10m)
16.Expalin codes of Turing Machine kinds.(10m)
17. write kind two grammer with all productions
a) that generate the language(0(power n)1(ower n)/n>=0}.(5m)
b)write a short note on application of finite automata.(5m)

Earning:   Approval pending.