Punjab University 2008 B.B.A B.ECOMTER SCIENCE AND ENGINEERING - Question Paper
Tuesday, 07 May 2013 09:15Web
THEORY OF calculation ques. paper
FIFTH SEMESTER
B.E. COMPUTER SCIENCE AND ENGINEERING
CS332 - THEORY OF calculation
TIME: 3 HOURS MAXIMUM : 100 MARKS
ans ALL ques.
PART A – (10 X two = 20 MARKS)
1. What is the difference ranging from DFA and NFA?
2. provide regular set for the subsequent expression: 1(01)*(10)*1
3. For the grammar G described by S->AB, D->a,A->Aa,A->bB,B->Sb, provide derivation tree for the sentential form babab
4. provide pumping lemma to prove that provided language L is not situation free.
5. provide formal definition of PDA.
6. provide an example of a language accepted by a PDA but not by DPDA.
7. Prove that the function f(n)=n-1 is computable.
8. Design a Turning machine to calculate n mod 2.
9. What is undecidability?
10. Differentiate ranging from recursive and recursively enumerable language.
PART B – (5 x 16 = 80 MARKS)
11. Construct a situation free grammar for the provided language L={anbn|/n>=1}U{amb2m/m>=1} and hence a PDA accepting L by empty stack (16)
12.a) Prove the equivalence of NFA and DFA. (8 )
b) Prove that a balanced parenthesis is not a regular language. (8 )
(OR)
12.a) discuss in detail with an example the conversion of NDFA to DFA (8 )
b) Show that L = {an! : n>=0} is not regular. (8 )
13.a) discuss in detail the ambiguity in situation free grammar. (8 )
b) Convert the grammar S->ABb|a, A->aaA|B, B->bAb into greibach normal form. (8 )
(OR)
13.a) Construct a situation free grammar for the languages L(G1)={aib2i/I>0} and L(G2)={anban/n>0} (8 )
(b) Prove that {op | p is prime} is not situation free. (8 )
14. Construct a Turing Machine to do the proper subtraction (16)
(OR)
14.a) Construct a Turning machine to perform multiplication (8 )
b) Prove the equivalence of two-way infinite tape with standard Turing machine. (8 )
15.a) explain in detail about universal Turing machine. (8 )
b) Prove that halting issue is undecidable. (8 )
(OR)
15.a) Prove that the union and intersection of 2 recursive languages are also recursive. (8 )
b) Prove that there exists an recursively enumerable language whose complement is not recursively enumerable. (8 )
Earning: Approval pending. |