GATE CSE 2005 | GATE CSE Year Wise Previous Years Questions

PREVIOUS NEXT

GATE CSE 2005

MCQ (Single Correct Answer)

-0.3

A common property of logic programming languages and functional languages is:

both are procedural languages

both are based on l-calculus

both are declarative

both use Horn-clauses

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Consider three decision problems $${P_1},$$ $${P_2}$$ and $${P_3}.$$ It is known that $${P_1}$$ is decidable and $${P_2}$$ is un-decidable. Which of the following is TRUE?

$${P_3}$$ is decidable if $${P_1}$$ is reducible to $${P_3}$$

$${P_3}$$ is in-decidable if $${P_3}$$ is reducible to $${P_2}$$

$${P_3}$$ is un-decidable if $${P_2}$$ is reducible to $${P_3}$$

$${P_3}$$ is decidable if $${P_3}$$ is reducible to $${P_2}'s$$ complement

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Let $${L_1}$$ be a recursive language, and Let $${L_2}$$ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

$$\overline {{L_1}} $$ is recursive and $$\overline {{L_2}} $$ is recursively enumerable

$$\overline {{L_1}} $$ is recursive and $$\overline {{L_2}} $$ is not recursively enumerable

$$\overline {{L_1}} $$ and $$\overline {{L_2}} $$ are recursively enumerable

$$\overline {{L_1}} $$ is recursively enumerable and $$\overline {{L_2}} $$ is recursive

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Consider the language :
$${L_1}\, = \left\{ {w\,{w^R}\,\left| {w \in \left\{ {0,1} \right\}{}^ * } \right.} \right\}$$
$${L_2}\, = \left\{ {w\, \ne {w^R}\,\left| {w \in \left\{ {0,1} \right\}{}^ * } \right.} \right\}$$ where $$ \ne $$ is a special symbol
$${L_3}\, = \left\{ {w\,w\,\left| {w \in \left\{ {0,1} \right\}{}^ * } \right.} \right\}$$

Which one of the following is TRUE?

$${L_1}$$ $$=$$ is a deterministic $$CFL$$

$${L_2}$$ $$=$$ is a deterministic $$CFL$$

$${L_3}$$ is a $$CFL,$$ but not a deterministic $$CFL$$

$${L_3}$$ IS A DETERMINISTIC $$CFL$$

PREVIOUS NEXT

GATE CSE Papers

2024