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 9 English

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

Your input ____
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 15 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
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12