GATE Prev Year : Theory of Computation Test-2

Attempt now to get your rank among 1004 students!

Question 1

The regular expression 0*(10*)* denotes the same set as

• A(1*0)*1*
• B0+(0+10)*
• C(0+1)*10(0+1)*
• DNone of the above

Question 2

Which of the following pairs have DIFFERENT expressive power?

• ADeterministic finite automata (DFA) and Non-deterministic finite automata (NFA)
• BDeterministic push down automata (DPDA) and Non-deterministic push down automata (NPDA)
• CDeterministic single-tape Turing machine and Non-deterministic single-tape Turing machine
• DSingle-tape Turing machine and multi-tape Turing machine

Question 3

Let N_f and N_p denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let D_f and D_p denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?

• AD_f⊂N_f and D_p⊂ N_p
• BD_f⊂N_f and D_p = N_p
• CD_f = N_f and D_p = N_p
• DD_f = N_f and D_p⊂ N_p

Question 4

Consider the languages
L₁ = {aⁿbⁿc^m | n, m > 0} and L₂ = {aⁿb^mc^m | n, m > 0}
Which one of the following statements is FALSE?

• AL₁∩ L₂ is a context-free language
• BL₁∪L₂ is a context-free language
• CL₁ and L₂ are context-free language
• DL₁∩L₂ is a context sensitive language

Question 5

Consider the machine M:
 
The language recognized by M is:

• A{w ∈{a, b}* | every a in w is followed by ex ­actly two b’s}
• B{w ∈{a, b}* | every a in w is followed by at least two b’s}
• C{w ∈{a, b}* | w contains the substring ‘abb’}
• D{w ∈{a, b}* | w does not contain ‘aa’ as a substring}

Question 6

Let P, Q and R be three atomic prepositional assertions. Let X denote (P v Q) → R and Y denote (P → R) v (Q → R). Which one of the following is a tautology?

• AX ≡ Y
• BX → Y
• CY → X
• D ¬ Y → X

• 1004 attempts
• 7 upvotes
• 53 comments