1
GATE CSE 2018
Numerical
+2
-0
Given a language $$𝐿,$$ define $${L^i}$$ as follows: $${L^0} = \left\{ \varepsilon \right\}$$
$${L^i} = {L^{i - 1}}.\,\,L$$ for all $$i > 0$$

The order of a language $$L$$ is defined as the smallest k such that $${L^k} = {L^{k + 1}}.$$ Consider the language $${L_1}$$ (over alphabet $$0$$) accepted by the following automaton.

GATE CSE 2018 Theory of Computation - Finite Automata and Regular Language Question 34 English

The order of $${L_1}$$ is _____.

Your input ____
2
GATE CSE 2018
MCQ (Single Correct Answer)
+2
-0.6
Let $$N$$ be an $$NFA$$ with $$n$$ states. Let $$k$$ be the number of states of a minimal $$DFA$$ which is equivalent to $$N.$$ Which one of the following is necessarily true?
A
$$k \ge {2^n}$$
B
$$k \ge n$$
C
$$k \le {n^2}$$
D
$$k \le {2^n}$$
3
GATE CSE 2016 Set 2
MCQ (Single Correct Answer)
+2
-0.6
Consider the following languages : $$$\eqalign{ & {L_1} = \left\{ {{a^n}{b^m}{c^{n + m}}:m,n \ge 1} \right\} \cr & {L_2} = \left\{ {{a^n}{b^n}{c^{2n}}:n \ge 1} \right\} \cr} $$$

Which one of the following is TRUE?

A
Both $${L_1}$$ and $${L_2}$$ are context-free.
B
$${L_1}$$ is context-free while $${L_2}$$ is not context-free.
C
$${L_2}$$ is context-free while $${L_1}$$ is not context-free.
D
Neither $${L_1}$$ nor $${L_2}$$ is context-free.
4
GATE CSE 2016 Set 2
MCQ (Single Correct Answer)
+2
-0.6
Consider the following two statements :

$$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,$$ If all states of an $$NFA$$ are accepting states then the language accepted by the
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ $$NFA$$ is $$\sum {^ * } .$$
$$\,\,\,\,\,{\rm I}{\rm I}.\,\,\,\,\,$$ There exists a regular language $$A$$ such that for all languages $$B,A \cap B$$ is
$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ regular.

Which one of the following is CORRECT?

A
Only $${\rm I}$$ is true
B
Only $${\rm II}$$ is true
C
Both $${\rm I}$$ and $${\rm II}$$ are true
D
Both $${\rm I}$$ and $${\rm II}$$ are false

GATE CSE Subjects

Browse all chapters by subject

Software Engineering
Web Technologies