# TOC |Gate-2007| Previous Year Questions| Set-14

TOC |Gate-2007| Theory of Computation ( Automata)

1. 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.

1. 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.

1. 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

1. 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.

1. 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}+}

1. 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

1. 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)

1. 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