CS/IT Gate Subject



Automata GATE CS and IT previous year questions with answer


Ques 21 Gate 2019

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?

A

3

B

5

C

9

D

24



Ques 22 Gate 2018

Consider the following languages:

I. {ambncpdq ∣ m + p = n + q, where m, n, p, q ≥ 0}
II. {ambncpdq ∣ m = n and p = q, where m, n, p, q ≥ 0}
III. {ambncpdq ∣ m = n = p and p ≠ q, where m, n, p, q ≥ 0}
IV. {ambncpdq ∣ mn = p + q, where m, n, p, q ≥ 0}


Which of the above languages are context-free?

A

I and IV only

B

I and II only

C

II and III only

D

II and IV only



Ques 23 Gate 2017 Set-2

The minimum possible number of states of a deterministic finite automaton that accepts a regular language L = {w1aw2 | w1, w2 ∈{a,b}* , |w1| = 2, w2>=3} is_______


a is the correct answer.


Ques 24 Gate 2017 Set-2

Identity the language generated by following grammar where S is the start variable.

S --> XY
X --> aX | a
Y --> aYb | ∈

A

{am bn| m>=n, n>0 }

B

{am bn| m>=n, n>=0 }

C

{am bn | m>n, n>=0 }

D

{am bn| m>n, n>0 }



Ques 25 Gate 2017 Set-2

Let L1 and L2 be any context-free language and R be any regular language. Then, which of the following is correct ?

I. L1 ∪ L2 is context-free.
II. L1' is context-free.
III. L1-R is context-free.
IV. L1 ∩ L2 context-free.

A

I only

B

I and III only

C

II and IV only

D

I, II and IV only



Ques 26 Gate 2017 Set-1

Consider the following grammar:

stmt -> if expr then else expr; stmt | ε
expr -> term relop term | term
term -> id | number
id -> a | b | c
number -> [0-9]


where relop is a relational operate (e.g < >, ….), ε refers to the empty statement, and if ,then, else are terminals. Consider a program P following the above grammar containing ten if terminals. The number of control flows paths in P is ____________. For example, the program

if e1 then
    e2
else
    e3

has 2 control flow paths, e1 -> e2 and e1 -> e3


a is the correct answer.


Ques 27 Gate 2017 Set-1

Consider the language L given by the regular expression (a + b)*b(a +b) over the alphabet {a, b}. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting L is ______.


4 is the correct answer.


Ques 28 Gate 2017 Set-1

Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total functional from A* to B* .We say f is computable if there exists a Turning machine M which given an input x in A*, always halts with f(x) on its tape. Let Lf denotes the language {x#f(x)|x∈A*}. Which of the following statements is true?

A

f if computable if and only if Lf is recursive.

B

f if computable if and only if Lf is recursive enumerable.

C

if f is computable then Lf is recursive, but not conversely.

D

if f is computable then Lf is recursively enumerable, but not conversely.



Ques 29 Gate 2017 Set-1

Consider the following languages over the alphabet ∑= {a,b,c}.
Let L1 ={anbncm | m, n >= 0 } and
L2 = {ambncn| m, n >= 0}.

Which of the following are context-free languages ?
I. L1 ∪ L2
II. L1 ∩ L2

A

I only

B

II only

C

I and II

D

Neither I nor II



Ques 30 Gate 2017 Set-1

If G is grammar with productions

S → SaS | aSb | bSa | SS | ∈


where S is the start variable, then which one of the following is not generated by G?

A

abab

B

aaab

C

abbaa

D

babba