1
GATE CSE 2014 Set 3
+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?
A
Both $${2^{\sum {{}^ * } }}$$ and $$\sum {^ * }$$ are countable
B
$${2^{\sum {{}^ * } }}$$ is countable and $$\sum {^ * }$$ is uncountable
C
$${2^{\sum {{}^ * } }}$$ is uncountable and $$\sum {^ * }$$ is countable
D
Both $${2^{\sum {{}^ * } }}$$ and $$\sum {^ * }$$ are uncountable
2
GATE CSE 2012
+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?
A
$$1, 2,3,4$$
B
$$1,2$$
C
$$2,3,4$$
D
$$3,4$$
3
GATE CSE 2008
+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
A
$$1$$ and $$2$$
B
$$1$$ and $$4$$
C
$$2$$ and $$3$$
D
$$2$$ and $$4$$
4
GATE CSE 1996
+1
-0.3
Which of the following statements is false?
A
The halting problem for Turing machine is un-decidable
B
Determining whether ambiguity a context free grammar is un-decidable
C
Given two arbitrary context free grammars $${G_1}$$ and $${G_2}$$ whether $$L\left( {{G_1}} \right) = L\left( {{G_2}} \right)$$
D
Given two regular grammars $${{G_1}}$$ and $${{G_2}},$$ it is un-decidable whether $$L\left( {{G_1}} \right) = L\left( {{G_2}} \right)$$
GATE CSE Subjects
EXAM MAP
Medical
NEET