How are Turing machines tested in GATE Theory of Computation?

GATE tests Turing machine configurations, transition functions, and the languages they accept. Questions ask whether a given TM accepts a specific string, what language a TM recognizes, and how multi-tape TMs compare to single-tape TMs in terms of computational power and time complexity.

What is the halting problem and why is it undecidable in GATE TOC?

The halting problem asks whether a given Turing machine M halts on input w. It is undecidable — no Turing machine can solve it for all inputs. GATE tests this using diagonalization proof and reduction. Problems reducible from the halting problem are also undecidable.

What is Rice's theorem and how is it applied in GATE CS?

Rice's theorem states that any non-trivial property of the language recognized by a Turing machine is undecidable. GATE tests this by asking whether problems like "does TM M accept an empty language", "does L(M) contain a specific string", or "is L(M) regular" are decidable. All such non-trivial language properties are undecidable by Rice's theorem.

What is the difference between recursive and recursively enumerable languages in GATE?

A recursive (decidable) language has a Turing machine that always halts and accepts or rejects. A recursively enumerable (RE) language has a TM that accepts strings in the language but may loop forever on strings not in the language. GATE tests closure properties: recursive languages are closed under complement, while RE languages are not.

CS/IT Gate Subject

Aptitude and Reasoning
Engineering Mathematics
C Programming
Data Structure
Design Algorithm Analysis
Operating System
Computer Network
Digital Logic Design
Compiler Design
Database Management System
Theory of Computation

Automata GATE previous year questions with answer

1 2 3 4 5

Ques 40 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).

Finite

Non-finite but regular

Context-free but not regular

Recursive but not context-free

(b) is the correct answer.

Ques 41 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?

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

{(abⁿcb^m₁cb^m₂...cb^m_n | n, m1, m2, ....., mn >= 1 }

{(ab)ⁿ(cb^m)ⁿ | n >= 1 }

{(ab)ⁿ(cbⁿ)^m | m, n >= 1 }

(b) is the correct answer.

Ques 42 Gate 2017 Set-1

Consider the following grammar

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

Which is FOLLOW(Q)?

{R}

{w}

{w, y}

{w, ∉}

(FIRST and FOLLOW) is the correct answer.

Ques 43 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 44 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?

Both G1 and G2

Only G1

Only G2

Neither G1 nor G2

(CFG) is the correct answer.

PROCESSED

Ques 45 Gate 2016 Set-2

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

S → AB
A → Aa | b
B → c

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

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

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

(Grammar) is the correct answer.

PROCESSED

Ques 46 Gate 2016 Set-2

Consider the following languages.

L₁ = {(M) | M takes at least 2016 steps on some input},
L₂ = {(M) | M takes at least 2016 steps on all inputs} and
L₃ = {(M) | M accepts ε},

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

L₁ is recursive and L₂, L₃ are not recursive

L₂ is recursive and L₁, L₃ are not recursive

L₁, L₂ are recursive and L₃ is not recursive

L₁, L₂,L₃ are recursive

(Turing Machine) is the correct answer.

PROCESSED

Ques 47 Gate 2016 Set-2

Consider the following languages:

L₁= {aⁿb^mc^n+m : m, n >= 1}
L₂= {aⁿbⁿc²ⁿ : n >= 1}

Which one of the following is TRUE?

Both L₁ and L₂ are context-free.

L₁ is context-free while L₂ is not context-free.

L₂ is context-free while L₁ is not context-free.

Neither L₁ nor L₂ is context-free.

(CFG) is the correct answer.

PROCESSED

Ques 48 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?

Only I is true

Only II is true

Both I and II are true

Both I and II are false

(DFA) is the correct answer.

PROCESSED

Ques 49 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

I only

I and III only

I and IV only

I, II and III only

(L) is the correct answer.

Given:
L₁ is a Regular language.
L₂ is a Context-free language.
L₃ is a Recursive language.
L₄ is a Recursively enumerable language.
To find:
Which of the given statements (I, II, III, IV) is/are TRUE.
Solution:
Let me check statement I: L₃' ∪ L₄ is recursively enumerable.
L₃ is recursive, and recursive languages are closed under complementation.
So, L₃' is also recursive.
Every recursive language is also recursively enumerable, so L₃' is recursively enumerable.
Since recursively enumerable languages are closed under union, L₃' ∪ L₄ must be recursively enumerable.
So, statement I is TRUE.
Now let me check statement II: L₂ ∪ L₃ is recursive.
L₂ is context-free, and every context-free language is recursive.
L₃ is already given as recursive.
Since recursive languages are closed under union, the union of two recursive languages is recursive.
So, statement II is TRUE.
Next, let me check statement III: L₁* ∪ L₂ is context-free.
L₁ is regular, and regular languages are closed under Kleene star.
So, L₁* is regular.
Every regular language is context-free, which means L₁* is also context-free.
Since context-free languages are closed under union, L₁* ∪ L₂ is context-free.
So, statement III is TRUE.
Now let me check statement IV: L₁ ∪ L₂' is context-free.
Context-free languages are not closed under complementation, so L₂' need not be context-free.
Therefore, L₁ ∪ L₂' is not necessarily context-free.
So, statement IV is FALSE.
Thus, statements I, II, and III are TRUE.
Answer:
(D) I, II and III only

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Subject

Automata GATE previous year questions with answer

Question Options

Sign in to ExamPrev