# TOC |Gate-2020| Previous Year Questions| Set-1 TOC |Gate-2020| Theory of Computation ( Automata)

1. Consider the language and the following statements.

1. L is deterministic context-free.
2. L is context-free but not deterministic context-free.
3. L is not LL(k) for any k.

Which of the above statements is/are TRUE? [GATE – 2020]

a. 2 only
b. 3 only
c. 1 only
d. 1 and 3 only

TOC |Gate-2020|

2. Consider the following statements.

I.If L1 U L2is regular, then both L1 and L2 must be regular.
II.The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE? [GATE – 2020]

a. Both I and II
b. II only
c. Neither I nor II
d. I only

3. Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s? [GATE – 2020]

a. 10*(0*10*10*)*
b. (0*10*10*)*10*
c. ((0 + 1)*1(0 + 1)*1)*10*
d. (0*10*10*)*0*1

4. Which of the following languages are undecidable? Note that indicates encoding of the Turing machine M. [GATE – 2020]

L1   =< M >| L (M) =
L2 = { < M,w,q>| M on input w reaches state q in exactly 100 steps }
L3 = {<M>| L (M) is not recursive }
L4 = {<M>| L (M) contains atleast 21 members }

a. L2 and L3 only
b. L1 and L3 only
c. L2, L3 and L4 only
d. L1, L3 and L4 only

Theory of Computation |Gate-2020|

5. Consider the following language.
L = {x ∈ {a,b}* | number of a’s in x is divisible by 2 but not divisible by 3}
The minimum number of states in a DFA that accepts L is ______. [GATE – 2020]

a. 6
b. 7
c. 8
d. 9

TOC |Gate-2020|

6. Consider the following languages.

L1 = {wxyx | w,x,y ∈ (0 + 1)+}
L2 = {xy | x,y ∈ (a + b)*, |x| = |y|, x ≠ y}
Which one of the following is TRUE? [GATE – 2020]

a. L1 is context-free but not regular and L2 is context-free.
b. L1 is context-free but L2 is not context-free.
c. L1 is regular and L2 is context-free.
d. Neither L1 nor L2 is context-free.