GATE CSE 1996 | GATE CSE Year Wise Previous Years Questions

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)$$

GATE CSE 1996

MCQ (Single Correct Answer)

-0.3

Which two of the following four regular expressions are equivalent?
(i) $${\left( {00} \right)^ * }\left( {\varepsilon + 0} \right)$$
(ii) $${\left( {00} \right)^ * }$$
(iii) $${0^ * }$$
(iv) $$0\,\,{\left( {00} \right)^ * }$$

(i) and (ii)

(ii) and (iii)

(i) and (iii)

(iii) and (vi)

GATE CSE 1996

MCQ (Single Correct Answer)

-0.3

Let $$L \subseteq \sum {^{^ * }\,} $$ where $$\,\sum { = \,\,\left\{ {a,b} \right\}\,\,} $$ which of the following is true?

$$L = \,\,\,\left\{ {\left. x \right|\,\,\,x} \right.$$ has an equal number of $$a's$$ and $$\,\left. {b's} \right\}$$ is regular

$$L = \left\{ {{a^n}{b^n}\left| {n \ge 1} \right.} \right\}$$ is regular

$$L = \,\,\,\left\{ {\left. x \right|\,\,\,x} \right.\,$$ has more $$a's$$ than $$\left. {b's} \right\}$$ is regular

$$L = \left\{ {{a^m}{b^n}\left| {m \ge 1,\,n \ge 1} \right.} \right\}$$ is regular

GATE CSE 1996

MCQ (Single Correct Answer)

-0.6

If $${L_1}$$ and $${L_2}$$ are context free languages and $$R$$ a regular set, one of the languages below is not necessarily a context free language. Which one?

$${L_1}$$$${L_2}$$

$${L_1}\, \cap \,{L_2}$$

$${L_1}\, \cap \,R$$

$${L_1}\, \cup \,{L_2}$$

PREVIOUS NEXT

GATE CSE Papers

2024