TOC |Gate-2007| Theory of Computation ( Automata)
- Which of the following problems is undecidable? [GATE – 2007]
a. Membership problem for CFGs.
b. Ambiguity problem for CFGs.
c. Finiteness problem for FSAs.
d. Equivalence problem for FSAs.
Answer : b)
- Which of the following is TRUE? [GATE – 2007]
a. Every subset of a regular set is regular.
b. Every finite subset of a non-regular set is regular.
c. The union of two non-regular sets is not regular.
d. Infinite union of finite sets is regular.
Answer : b)
- A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has: [GATE – 2007]
a. 15 states
b. 11 states
c. 10 states
d. 9 states
Answer : a)
- The language L = {0i21i | i≥0} over the alphabet {0,1, 2} is: [GATE – 2007]
a. not recursive.
b. is a regular language.
c. is recursive and is a deterministic CFL.
d. is not a deterministic CFL but a CFL.
Answer : c)
- Which of the following languages is regular? [GATE – 2007]
a. {wwR|w ∈ {0,1}+}
b. {wwRx|x, w ∈ {0,1}+}
c. {xwwR|x, w ∈ {0,1}+}
d. {wxwR|x, w ∈ {0,1}+}
Answer : d)
- Consider the following Finite State Automaton.
The language accepted by this automaton is given by the regular expression : [GATE – 2007]
a. 1
b. 2
c. 3
d. 4
Answer : c)
- Consider the grammar given below S → x B | y A A → x | x S | y A A B → y | y S | y B B Consider the following strings. (i) xxyyx (ii) xxyyxy (iii) xyxy (iv) yxxy (v) yxx (vi) xyx Which of the above strings are generated by the grammar ? [GATE – 2007]
a. (ii), (iii), and (iv)
b. (ii), (v), and (vi)
c. (i), (ii), and (iii)
d. (i), (iii), and (iv)
Answer : a)
- Consider the following grammars. Names representing terminals have been specified in capital letters.
G1 : stmnt →WHILE(expr)stmnt
stmnt → OTHER
expr →ID
G2 : WHILE(expr)stmnt
stmnt → OTHER
expr→expr + expr
expr→expr * expr
expr →ID
Which one of the following statements is true? [GATE – 2007]
a. G1 is context-free but not regular and G2 is regular
b. G2 is context-free but not regular and G1 is regular
c. Both G1 and G2 are regular
d. Both G1 and G2 are context-free but neither of them is regular
Answer : d)
TOC |Gate-2007|