TOC |Gate-2011| Theory of Computation ( Automata)
- 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
Answer : c)
- 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
Answer : b)
- 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)
Answer : d)
- 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
Answer : a)
TOC |Gate-2011|