CS/IT Gate Subject



Automata GATE CS and IT previous year questions with answer


Ques 31 Gate 2017 Set-1

Consider the following grammar over the alphabet {a,b,c} given below, S and T are non-terminals.

G1: S-->aSb|T
T--> cT|∈
G2: S-->bSa|T
T--> cT|∈

The language L1(G1) ∩ L2(G2).

A

Finite

B

Non-finite but regular

C

Context-free but not regular

D

Recursive but not context-free



Ques 32 Gate 2017 Set-1

Consider the following context-free grammar over the alphabet ∑ = {a, b, c} with S as the start symbol:

S → abScT | abcT
T → bT | b


Which of the following represents the language generated by the above grammar?

A

{(ab)n(cb)n | n >= 1 }

B

{(abncbm1cbm2...cbmn | n, m1, m2, ....., mn >= 1 }

C

{(ab)n(cbm)n | n >= 1 }

D

{(ab)n(cbn)m | m, n >= 1 }



Ques 33 Gate 2017 Set-1

Consider the following grammar

P→xQRS
Q→yz|z
R→ w|∈
S→y

Which is FOLLOW(Q)?

A

{R}

B

{w}

C

{w, y}

D

{w, ∉}



Ques 34 Gate 2016 Set-2

The number of states in the minimum sized DFA that accepts the language defined by the regular expression

(0+1)*(0+1)(0+1)*


is __________________


a is the correct answer.


Ques 35 Gate 2016 Set-2

A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example,

int a[10][3];
The grammars use D as the start symbol, and use six terminal symbols int ; id [ ] num.

Grammar G1
D → int L;
L → id [E
E → num]
E → num] [E

Grammar G2
D → int L;
L → id E
E → E[num]
E → [num]

Which of the grammars correctly generate the declaration mentioned above?

A

Both G1 and G2

B

Only G1

C

Only G2

D

Neither G1 nor G2



Ques 36 Gate 2016 Set-2

Which one of the following grammars is free from left recursion?

A

S → AB
A → Aa | b
B → c

B

S → Ab | Bb | c
A → Bd | ε
B → e

C

S → Aa | B
A → Bb | Sc | ε
B → d

D

S → Aa | Bb | c
A → Bd | ε
B → Ae | ε



Ques 37 Gate 2016 Set-2

Consider the following languages.

L1 = {(M) | M takes at least 2016 steps on some input},
L2 = {(M) | M takes at least 2016 steps on all inputs} and
L3 = {(M) | M accepts ε},

where for each Turing machine M, denotes a specific encoding of M. Which one of the following is TRUE?

A

L1 is recursive and L2, L3 are not recursive

B

L2 is recursive and L1, L3 are not recursive

C

L1, L2 are recursive and L3 is not recursive

D

L1, L2,L3 are recursive



Ques 38 Gate 2016 Set-2

Consider the following languages:

L1= {anbmcn+m : m, n >= 1}
L2= {anbnc2n : n >= 1}

Which one of the following is TRUE?

A

Both L1 and L2 are context-free.

B

L1 is context-free while L2 is not context-free.

C

L2 is context-free while L1 is not context-free.

D

Neither L1 nor L2 is context-free.



Ques 39 Gate 2016 Set-2

Consider the following two statements:

I. If all states of an NFA are accepting states then the language accepted by the NFA is Σ* .
II. There exists a regular language A such that for all languages B, A ∩ B is regular.

Which one of the following is CORRECT?

A

Only I is true

B

Only II is true

C

Both I and II are true

D

Both I and II are false



Ques 40 Gate 2016 Set-2

Consider the following types of languages:

L1 Regular,
L2: Context-free,
L3: Recursive,
L4: Recursively enumerable.

Which of the following is/are TRUE?

I. L3' U L4 is recursively enumerable
II. L2 U L3 is recursive
III. L1* U L2 is context-free
IV. L1 U L2' is context-free

A

I only

B

I and III only

C

I and IV only

D

I, II and III only