# TOC |Gate-2011| Previous Year Questions| Set-10 TOC |Gate-2011| Theory of Computation ( Automata)

1. Consider the languages L1,L2 and L3 as given below. Which of the following statements is NOT TRUE?  [GATE – 2011]

a. Push Down Automate (PDA) can be used to recognize L1 and L2
b. L1 is a regular language
c. All the three languages are context free
d. Turing machines can be used to recognize all the languages

1. Definition of a language L with alphabet {a} is given as following.L = {ank | k>0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L? [GATE – 2011]

a. k+1
b. n+1
c. 2n+1
d. 2k+1

1. Which of the following pairs have DIFFERENT expressive power? [GATE – 2011]

a. Deterministic finite automata (DFA) and Non-deterministic finite automata (NFA)
b. Deterministic single-tape Turning machine and Non-deterministic single tape Turning machine
c. Single-tape Turning machine and multi-tape Turning machine
d. Deterministic push down automata (DPDA) and Non-deterministic push down automata (NFDA)

1. Let P be a regular language and Q be a context-free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q* and Q be [pnqn | n ∈ N]). Then which of the following is ALWAYS regular? [GATE – 2011]

a. Σ* – P
b. P – Q
c. P ∩ Q
d. Σ* – Q