Theory of Computer Science Question Paper - Dec 18 - Computer Engineering (Semester 5)

440views

written 6.9 years ago by

teamques10 ★ 70k

Theory of Computer Science - Dec 18

Computer Engineering (Semester 5)

Total marks: 80
Total time: 3 Hours INSTRUCTIONS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Draw neat diagrams wherever necessary.

1.a. Explain Chomsky Hierarchy.

(5 marks) 00

1.b. Difference between PDA and NPDA.

(5 marks) 00

1.c. Define regular expression and give regular expression for

i) Set of all strings over {0,1} that end with 1 and has no substring 00

(5 marks) 00

1.d. Explain Halting Problem

(5 marks) 00

2.a. Define the finite state machine to determine the ternary number (base 3) is divisible 5.

(10 marks) 00

2.b. Give and explain formal definition of Pumping Lemma for Regular Language and prove that the following language is not regular

enter image description here

(10 marks) 00

3.a. Construct PDA accepting the language enter image description here

(10 marks) 00

3.b. Consider the following grammar

enter image description here

for the string 'ibtaeibta' find the following :

(i) Leftmost Derivation

(ii)Rightmost derivation

(iii)Parse tree

(iv)Check if above grammar is ambiguous.

(10 marks) 00

4.a. Construct TM to check wellformness of parenthesis.

(10 marks) 00

4.b. Convert following CFG and CNF

enter image description here

(10 marks) 00

5.a. Convert (0+1)(10)*(0+1) into NFA with $\epsilon$-moves and obtain DFA.

(10 marks) 00

5.b. Construct Moore and Mealy machine to convert each occurence of 100 by 101.

(10 marks) 00

6 Write short note on any four -

(a)Closure properties of Context Free Language

(b)Applications of Regular expression and Finite automata.

(c)Rice's Theorem

(d)Moore and Mealy Machine.

(e)Universal Turing Machine

(20 marks) 00

ADD COMMENT EDIT