# TOC |Gate-2012| Previous Year Questions| Set-9

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

1. Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below.

The missing arcs in the DFA are  : [GATE – 2012]

a.

b.

c.

d.

2. Given the language L ={ab,aa,baa}, which of the following strings are in L *? 1)abaabaaabaa 2)aaaabaaaa 3)baaaaabaaaab 4)baaaaabaa  : [GATE – 2012]

a. 1, 2 and 3
b. 2, 3 and 4
c. 1, 2 and 4
d. 1, 3 and 4

3. Which of the following problems are decidable? [GATE – 2012]

1) Does  a given program ever produce an output?
2) If L is a context-free language, then, is L’ also context-free?
3) If L is  a regular language, then, is L’ also regular?
4) If L is a recursive language, then, is L’ also recursive?

a. 1,2,3,4
b. 1,2
c. 2,3,4
d. 3,4

4. What is the complement of the language accepted by the NFA shown below? [GATE – 2012]

a. ∅
b. {ε}
c. a*
d. {a ,ε}