# TOC |Gate-2019| Previous Year Questions| Set-2 TOC |Gate-2019| Theory of Computation ( Automata)

1. If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular? [GATE – 2019]

a. Suffix (L) = {y ∈ Σ* such that xy ∈ L}
b. {wwR │w ∈ L}
c. Prefix (L) = {x ∈ Σ*│∃y ∈ Σ* such that xy ∈ L}
d. L ∙ LR = {xy │ x ∈ L, yR ∈ L}

1. For Σ = {a,b}, let us consider the regular language L = {x|x = a2+3k or x = b10+12k, k ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L? [GATE – 2019]

a. 3
b. 9
c. 5
d. 24

TOC |Gate-2019|

3. Consider the following sets:

S1.  Set of all recursively enumerable languages over the alphabet {0,1}
S2.  Set of all syntactically valid C programs
S3.  Set of all languages over the alphabet {0,1}
S4.  Set of all non-regular languages over the alphabet {0,1}

Which of the above sets are uncountable?   [GATE – 2019]

a. S2 and S3
b. S1 and S4
c. S3 and S4
d. S1 and S2

TOC |Gate-2019|

1. Which one of the following languages over Σ = {a,b} is NOT context-free? [GATE – 2019]

a. {wwR |w ∈ {a,b}*}
b. {wanwRbn |w ∈ {a,b}*, n ≥ 0}
c. {anbi | i ∈ {n, 3n, 5n}, n ≥ 0}
d. {wanbnwR |w ∈ {a,b}*, n ≥ 0}