GATE CSE 2014 Set 3 | Undecidability Question 4 | Theory of Computation

GATE CSE 2014 Set 3

MCQ (Single Correct Answer)

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

Both $${2^{\sum {{}^ * } }}$$ and $$\sum {^ * } $$ are countable

$${2^{\sum {{}^ * } }}$$ is countable and $$\sum {^ * } $$ is uncountable

$${2^{\sum {{}^ * } }}$$ is uncountable and $$\sum {^ * } $$ is countable

Both $${2^{\sum {{}^ * } }}$$ and $$\sum {^ * } $$ are uncountable

GATE CSE 2012

MCQ (Single Correct Answer)

-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, 2,3,4$$

$$1,2$$

$$2,3,4$$

$$3,4$$

GATE CSE 2008

MCQ (Single Correct Answer)

-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$$ and $$2$$

$$1$$ and $$4$$

$$2$$ and $$3$$

$$2$$ and $$4$$

GATE CSE 1996

MCQ (Single Correct Answer)

-0.3

Which of the following statements is false?

The halting problem for Turing machine is un-decidable

Determining whether ambiguity a context free grammar is un-decidable

Given two arbitrary context free grammars $${G_1}$$ and $${G_2}$$ whether $$L\left( {{G_1}} \right) = L\left( {{G_2}} \right)$$

Given two regular grammars $${{G_1}}$$ and $${{G_2}},$$ it is un-decidable whether $$L\left( {{G_1}} \right) = L\left( {{G_2}} \right)$$