Theory of Computation
Finite Automata and Regular Language
Marks 1Marks 2Marks 5
Push Down Automata and Context Free Language
Marks 1Marks 2
Undecidability
Marks 1Marks 2
Recursively Enumerable Language and Turing Machine
Marks 1Marks 2
1
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}$$
2
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 30 English

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

Your input ____
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
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