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

Set-15 TOC GATE 2006

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.

 00011011Q
0010   
01   1 
100    
11  0  

b.

 00011011Q
00 0  1
01 1   
10   0 
11 0   

c.

 00011011Q
00 1  0
01 1   
10  0  
11 0   

d.

 00011011Q
00 1  0
01   1 
100    
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|


Back to GATE-HOME


Spread the love

Leave a Comment

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