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 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
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 1
MCQ (Single Correct Answer)
+2
-0.6
Consider the transition diagram of a $$PDA$$ given below with input alphabet $$\sum {\, = \left\{ {a,b} \right\}} $$ and stack alphabet $$\Gamma = \left\{ {X,Z} \right\}.$$ $$Z$$ is the initial stack symbol. Let $$L$$ denote the language accepted by the $$PDA.$$ GATE CSE 2016 Set 1 Theory of Computation - Finite Automata and Regular Language Question 30 English

Which one of the following is TRUE?

A
$$L = \left\{ {{a^n}{b^n}|n \ge 0} \right\}$$ and is not accepted by any finite automata
B
$$L = \left\{ {{a^n}|n \ge 0} \right\} \cup \left\{ {{a^n}{b^n}|n \ge 0} \right\}$$ and is not accepted by any deterministic $$PDA$$
C
$$L$$ is not accepted by any Turing machine that halts on every input
D
$$L = \left\{ {{a^n}|n \ge 0} \right\} \cup \left\{ {{a^n}{b^n}|n \ge 0} \right\}$$ and is deterministic context-free
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12