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.
| 00 | 01 | 10 | 11 | Q | |
| 00 | 1 | 0 | |||
| 01 | 1 | ||||
| 10 | 0 | ||||
| 11 | 0 |
b.
| 00 | 01 | 10 | 11 | Q | |
| 00 | 0 | 1 | |||
| 01 | 1 | ||||
| 10 | 0 | ||||
| 11 | 0 |
c.
| 00 | 01 | 10 | 11 | Q | |
| 00 | 1 | 0 | |||
| 01 | 1 | ||||
| 10 | 0 | ||||
| 11 | 0 |
d.
| 00 | 01 | 10 | 11 | Q | |
| 00 | 1 | 0 | |||
| 01 | 1 | ||||
| 10 | 0 | ||||
| 11 | 0 |
Answer : 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
Answer : c)
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
Answer : d)
4. What is the complement of the language accepted by the NFA shown below? [GATE – 2012]
a. ∅
b. {ε}
c. a*
d. {a ,ε}
Answer : b)
TOC |Gate-2012|