Punjab University 2008 B.B.A B.ECOMTER SCIENCE AND ENGINEERING - Question Paper

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.