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

Set-15 TOC GATE 2006

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.

Answer : b)


  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.

Answer : b)


  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

Answer : a)


  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.

Answer : c)


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

Answer : d)


  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

Answer : c)


  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)

Answer : a)


  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

Answer : d)
TOC |Gate-2007|


Back to GATE-HOME


Spread the love

Leave a Comment

Your email address will not be published. Required fields are marked *