GTU Theory Of Computation - June 2014 Exam Question Paper

GTU Computer Engineering (Semester 6)
Theory Of Computation
June 2014

Total marks: --
Total time: --

INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

1 (a) Define One-to-one and Onto Functions. Also explain Compositions and Inverse of functions.

7 M

1 (b) Convert the following NFA- ? into FA.

7 M

2 (a) Let M₁ and M₂ be the FAs pictured below, recognizing languages L₁ and L₂ respectively.

Draw the FAs recognizing the following languages. L₁∩L₂
L₂-L₁.

7 M

2 (b) Define the Strong Principle of Mathematical Induction. Prove the following using mathematical Induction.
7+13+19+............+(6n+1)=n=(3n+4).

7 M

2 (c) Prove : The language accepted by any finite automaton is regular.

7 M

3 (a) Minimize the following DFA (If Possible).

7 M

3 (b) Let L be the language corresponding to the regular expression (011+1)* (01)*. Find the CFG generating L.

7 M

3 (c) Given the CFG G, find a CFG G' in Chomsky Normal form generating L(G) – { Λ}
S → A | B | C
A → aAa | B
B → bB | bb
C → aCaa | D
D → baD | abD | aa.

7 M

3 (d) Prove: The language pal={x∈{a,b}*|x=x²) cannot be accepted by any deterministic pushdown automaton.

7 M

4 (a) What is Pumping Lemma and Equivalence Relation ?

7 M

4 (b) Design and draw a deterministic PDA accepting strings with more a's than b's. Trace it for the string "abbabaa".

7 M

4 (c) Define CFG and Design a CFG for the following language.
L={x∈{0,1}*|n₀≠n₁(x)}.

7 M

4 (d) Attempt the following :
Draw FA for (a + b)* baaa.
Write a Regular Expression for the String of 0s and 1s in which number of 0s and 1s are even.

7 M

5 (a) Draw the TM to copy string and delete a symbol.

7 M

5 (b) Differentiate Regular Grammars and Context Sensitive Grammars.

7 M

5 (c) Define:
[1] Basic complexity Classes
[2] Primitive Recursive Functions
[3] The Time and Space Complexity of a Turing Machine

7 M

5 (d) Explain Polynomial Time Reductions and NP- Completeness.

7 M

More question papers from Theory Of Computation

SPONSORED ADVERTISEMENTS