What is the Post Correspondence Problem and how is it relevant to GATE?

The Post Correspondence Problem (PCP) is an undecidable problem where given two lists of strings, you must find an index sequence such that the concatenations of both lists match. GATE tests PCP as an example of an undecidable problem and uses it in reductions to prove other problems undecidable.

What is the Chomsky hierarchy and how is it tested in GATE CS?

The Chomsky hierarchy classifies grammars into Type 0 (unrestricted, recognized by TM), Type 1 (context-sensitive, recognized by linear bounded automaton), Type 2 (context-free, recognized by PDA), and Type 3 (regular, recognized by FA). GATE tests classification of languages into the correct Chomsky type and the automaton model for each.

How are language intersection and complement properties tested in GATE TOC?

GATE tests that regular languages are closed under all Boolean operations. Context-free languages are closed under union but NOT intersection or complement. If L is CFL and R is regular, then L ∩ R is always CFL. GATE also tests that if both L and its complement are RE, then L must be recursive (decidable).

How should I prepare Theory of Computation for GATE CS exam?

Focus on DFA/NFA construction and minimization, regular expression to automaton conversion, CFG and PDA design, pumping lemmas for both regular and CFL, Turing machine behavior, decidability (halting problem, Rice's theorem), and closure properties of all language classes. Practice all GATE previous year questions on ExamPrev with video solutions for maximum GATE TOC score.

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 53 Gate 2016 Set-2

Language L1 is defined by the grammar:
S1 -> aS1b | ε
Language L2 is defined by the grammar:
S2 -> abS2 | ε
Consider the following statements:

P: L1 is regular
Q: L2 is regular

Which one of the following is TRUE?

Both P and Q are true

P is true and Q is false

P is false and Q is true

Both P and Q are false

(Regular Grammar) is the correct answer.

Ques 54 Gate 2016 Set-1

Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y reduces to W, and Z reduces to X (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

W can be recursively enumerable and Z is recursive.

W an be recursive and Z is recursively enumerable.

W is not recursively enumerable and Z is recursive.

W is not recursively enumerable and Z is not recursive

(Recursive Language) is the correct answer.

Ques 55 Gate 2016 Set-1

Consider the following context-free grammars:

G1: S → aS|B, B → b|bB
G2: S → aA|bB, A → aA|B|ε, B → bB|ε

Which one of the following pairs of languages is generated by G1 and G2, respectively?

{a^mbⁿ |m > 0 or n > 0} and {a^mbⁿ |m > 0 and n > 0}

{a^mbⁿ |m > 0 and n > 0} and {a^mbⁿ |m > 0 or n ≥ 0}

{a^mbⁿ |m ≥ 0 or n > 0} and {a^mbⁿ |m > 0 and n > 0}

{a^mbⁿ |m ≥ 0 and n > 0} and {a ^mbⁿ |m > 0 or n > 0}

(CGF) is the correct answer.

Ques 56 Gate 2016 Set-1

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?

(0+1)*0011(0+1)* + (0+1)*1100(0+1)*

(0+1)* (00(0+1) *11+11(0+1)*00)(0+1)*

(0+1)*00(0+1) *+ (0+1) *11(0+1) *

00(0+1) *11+11(0+1)*00

(Regular Language) is the correct answer.

Ques 57 Gate 2016 Set-1

Which of the following decision problems are undecidable?

I. Given NFAs N₁ and N₂, is L(N₁)∩L(N₂) = Φ?
II. Given a CFG G = (N,Σ,P,S) and a string x ∈ Σ*, does x ∈ L(G)?
III. Given CFGs G₁ and G₂, is L(G₁) = L(G₂)?
IV. Given a TM M, is L(M) = Φ?

I and IV only

II and III only

III and IV only

II and IV only

(decidablility) is the correct answer.

Ques 58 Gate 2016 Set-1

Which of the following languages is generated by the given grammar?

S → aS|bS| ε

{aⁿb^m | m,n >= 0}

{w∈{a,b}* | w has equal number of a's and b's}

{aⁿ | n>=0} U {aⁿbⁿ | n>=0}

{a,b}*

(Grammar) is the correct answer.

Ques 59 Gate 2015 Set-1

For any two languages L₁ and L₂ such that L₁ is context free and L₂ is recursively enumerable but not recursive, which of the following is/are necessarily true?

I. L₁' (complement of L₁) is recursive
II. L₂' (complement of L₂) is recursive
III. L₁' is context-free
IV. L₁' ∪ L₂ is recursively enumerable

I only

III only

III and IV only

I and IV only

(CFG) is the correct answer.

L1 is context-free and L2 is recursively enumerable but not recursive.
Statement I — True: Every CFL is recursive, and recursive languages are closed under complement. Since L1 is CFL → L1 is recursive → L1'' is recursive.
Statement II — False: L2 is RE but not recursive. If L2'' were recursive, it would also be RE, and having both L2 and L2'' be RE would imply L2 is recursive — a contradiction. So L2'' is not recursive.
Statement III — False: CFLs are not closed under complementation. The complement of a CFL need not be context-free. For example, the complement of {aⁿbⁿcⁿ : n≥1} is CFL but not all CFL complements are CFLs. So L1'' is not necessarily context-free.
Statement IV — True: From I, L1'' is recursive, so L1'' is also RE. L2 is RE. RE languages are closed under union. Therefore L1'' ∪ L2 is RE.
Correct answer: D — I and IV only. Your page''s answer display is a bug showing "CFG" instead of D ✓

Ques 60 Gate 2014 Set-1

Which one of the following is TRUE?

The Language L={ aⁿ bⁿ | n≥ is regular }

The Language L={ aⁿ | n is prime }

The Language L={ w | w has 3k+1 b's for some k ∈ N with Σ ={a,b}} is regular

The Language L={ww | w ∈ Σ with Σ ={0,1}} is regular

(Regular Grammar) is the correct answer.

PROCESSED

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