TOC |Gate-2009| Previous Year Questions| Set-12

Set-15 TOC GATE 2006

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

  1. S → aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of : [GATE – 2009]

a. All palindromes.
b. All odd length palindromes.
c. Strings that begin and end with the same symbol.
d. All even length palindromes.

Answer : b)


  1. Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*? [GATE – 2009]

a. The set of all strings containing the substring 00.
b. The set of all strings containing at most two 0’s.
c. The set of all strings containing at least two 0’s.
d. The set of all strings that begin and end with either 0 or 1.

Answer : c)


  1. Which one of the following is FALSE? [GATE – 2009]

a. There is unique minimal DFA for every regular language.
b. Every NFA can be converted to an equivalent PDA.
c. Complement of every context-free language is recursive.
d. Every non-deterministic PDA can be converted to an equivalent deterministic PDA.

Answer : d)


  1. Given the following state table of an FSM with two states A and B, one input and one output:
Present State APresent State BInputNext State ANext State BOutput
000001
010100
100010
110100
001010
011001
101011
111001

If the initial state is A = 0, B=0, what is the minimum length of an input string which will take the machine to the state A=0, B=1 with Output=1?  [GATE – 2009]

a. 3
b. 4
c. 5
d. 6

Answer : a)


  1. The above DFA accepts the set of all strings over {0,1} that :[GATE – 2009]

a. begin either with 0 or 1
b. end with 0
c. end with 00
d. contain the substring 00

Answer : c)
TOC |Gate-2009|


Back to GATE-HOME


Spread the love

Leave a Comment

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