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
Theory of Computation
Operating Systems
Algorithms
Digital Logic
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages
Computer Organization
EXAM MAP
Joint Entrance Examination