1

GATE CSE 2016 Set 1

MCQ (Single Correct Answer)

+1

-0.3

Which of the following decision problems are undecidable?

$$\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ Given $$NFAs$$ $${N_1}$$ and $${N_2},$$ is $$L\left( {{N_1}} \right) \cap L\left( {{N_2}} \right) = \Phi ?$$

$$\,\,\,\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,\,\,\,\,\,$$Given a $$CFG\,G = \left( {N,\sum {\,,P} ,S} \right)$$ and string $$x \in \sum {^ * } ,$$ does

$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ $$x \in L\left( G \right)?$$

$$\,\,\,\,\,\,{\rm I}{\rm I}{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ Given $$CFGs\,\,{G_1}$$ and $${G_2},$$ is $$L\left( {{G_1}} \right) = L\left( {{G_2}} \right)?$$

$$\,\,\,\,\,\,{\rm I}V.\,\,\,\,\,\,\,\,\,\,$$ Given a $$TM$$ $$M,$$ is $$L\left( M \right) = \Phi ?$$

2

GATE CSE 2014 Set 3

MCQ (Single Correct Answer)

+1

-0.3

Let $$\sum \, $$ be a finite non - empty alphabet and let $${2^{\sum {{}^ * } }}$$ be the power set of $$\sum {{}^ * .\,} $$ Which one of the following is

**TRUE**?3

GATE CSE 2012

MCQ (Single Correct Answer)

+1

-0.3

Which of the following problems are decidable?

$$1.$$ Does a given program ever produce an output?

$$2.$$ If L is a context-free language, then, is $$\overline L $$ also context-free?

$$3.$$ If L is a regular language, then, is $$\overline L $$ also regular?

$$4.$$ If L is a recursive language, then, is $$\overline L $$ also recursive?

$$1.$$ Does a given program ever produce an output?

$$2.$$ If L is a context-free language, then, is $$\overline L $$ also context-free?

$$3.$$ If L is a regular language, then, is $$\overline L $$ also regular?

$$4.$$ If L is a recursive language, then, is $$\overline L $$ also recursive?

4

GATE CSE 2008

MCQ (Single Correct Answer)

+1

-0.3

Which of the following are decidable?

$$1.$$ Whether the intersection of two regular languages is infinite

$$2.$$ Whether a given context-free language is regular

$$3.$$ Whether two push-down automata accept the same language

$$4.$$ Whether a given grammar is context-free

$$1.$$ Whether the intersection of two regular languages is infinite

$$2.$$ Whether a given context-free language is regular

$$3.$$ Whether two push-down automata accept the same language

$$4.$$ Whether a given grammar is context-free

Questions Asked from Undecidability (Marks 1)

Number in Brackets after Paper Indicates No. of Questions

GATE CSE Subjects

Theory of Computation

Operating Systems

Algorithms

Database Management System

Data Structures

Computer Networks

Software Engineering

Compiler Design

Web Technologies

General Aptitude

Discrete Mathematics

Programming Languages