GATE CSE 2014 Set 2 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2014 Set 2

MCQ (Single Correct Answer)

-0.3

If $${L_1} = \left\{ {{a^n}\left| {n \ge \left. 0 \right\}} \right.} \right.$$ and $${L_2} = \left\{ {{b^n}\left| {n \ge \left. 0 \right\}} \right.} \right.,$$ consider
$$\left. {\rm I} \right)$$ $$\,\,\,{L_{1 \bullet }}{L_2}$$ is a regular language
$$\left. {\rm II} \right)$$ $$\,\,\,{L_{1 \bullet }}{L_2} = \left\{ {{a^n}{b^n}\left| {n \ge \left. 0 \right\}} \right.} \right.$$
Which one of the following is CORRECT?

Only $$\left( {\rm I} \right)$$

Only $$\left( {\rm II} \right)$$

Both $$\left( {\rm I} \right)$$ and $$\left( {\rm II} \right)$$

Neither $$\left( {\rm I} \right)$$ nor $$\left( {\rm II} \right)$$

GATE CSE 2014 Set 2

MCQ (Single Correct Answer)

-0.6

Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(110)'s$$ as $$(011)'s$$$$\left. \, \right\}$$. Let $${L_2} = \left\{ {w \in \left\{ {0,\,\,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(000)'s$$ as $$(111)'s$$$$\left. \, \right\}$$. Which one of the following is TRUE?

$${L_1}$$ is regular but not $${L_2}$$

$${L_2}$$ is regular but not $${L_1}$$

Both $${L_1}$$ and $${L_2}$$ are regular

Neither $${L_1}$$ nor $${L_2}$$ are regular

GATE CSE 2014 Set 2

MCQ (Single Correct Answer)

-0.3

Let $$A\,\,{ \le _m}\,\,B$$ denotes that language $$A$$ is mapping reducible (also known as many-to-one reducible) to language $$B.$$ Which one of the following is FALSE?

If $$A\,\,{ \le _m}\,\,B$$ and $$B$$ is recursive then $$A$$ is recursive.

If $$A\,\,{ \le _m}\,\,B$$ and $$A$$ is undecidable then $$B$$ is un-decidable.

If $$A\,\,{ \le _m}\,\,B$$ and $$B$$ is recursively enumerable then $$A$$ is recursively enumerable.

If $$A\,\,{ \le _m}\,\,B$$ and $$B$$ is not recursively enumerable then $$A$$ is not recursively enumerable.

GATE CSE Papers

2024