GATE CSE & IT

Which one of the following statements is equivalent to the following assertion? Turing machine $M$ decides the language $L \subseteq\{0,1\}$.

Let $\Sigma=\{a, b, c, d\}$ and let $L=\left\{a^i b^j c^k d^l \mid i, j, k, l \geq 0\right\}$. Which of the following constraints ensure(s) that the language $L$ is context-free?

Let $L_1$ and $L_2$ be two languages over a finite alphabet, such that $L_1 \cap L_2$ and $L_2$ are regular languages. Which of the following statements is/are always true?

Consider the following grammar where $S$ is the start symbol, and $a$ and $b$ are terminal symbols. $$ S \rightarrow a S b S|b S| \in $$ Which of the following statements is/are tr...

Consider the following context-free grammar $G$ : $$ \begin{aligned} & S \rightarrow a b a A B A b b a \\ & A \rightarrow a a B B A b \mid b B a b a a \\ & B \rightarrow a B b \mid...

Which of the following grammars is/are ambiguous?

The determinant of a $4 \times 4$ matrix $A$ is 3 . The value of the determinant of $2 A$ is $\_\_\_\_$ . (answer in integer)

Let $M$ be a non-deterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of the following options CANNOT be the number of states in the minimal determinist...

Let $\Sigma=\{1,2,3,4\}$ For $x \in \Sigma^*$, let prod $(x)$ be the product of symbols in $x$ modulo 7 . We take $\operatorname{prod}(\varepsilon)=1$, where $\varepsilon$ is the n...

Let $\Sigma=\{a, b, c\}$. For $x \in \Sigma^{\star}$, and $\alpha \in \Sigma$, let $\#_\alpha(x)$ denote the number of occurrences of a in $x$. Which one or more of the following o...

Which ONE of the following languages is accepted by a deterministic pushdown automaton?

Consider the following two languages over the alphabet $\{a, b\}$ : $$\begin{aligned} & L_1=\left\{\alpha \beta \alpha \mid \alpha \in\{a, b\}^{+} \text {AND } \beta \in\{a, b\}^{+...

Consider the two lists List-I and List-II given below: List - I List - II (i) Context free languages (a) Closed under union (ii) Recursive languages (b) Not closed under complement...

Let $G_1, G_2$ be Context Free Grammars (CFGs) and $R$ be a regular expression. For a grammar $G$, let $L(G)$ denote the language generated by $G$. Which ONE among the following qu...

Consider a finite state machine (FSM) with one input $X$ and one output $f$, represented by the given state transition table. The minimum number of states required to realize this...

Consider the following two languages over the alphabet $\{a, b, c\}$, where $m$ and $n$ are natural numbers. $$\begin{aligned} & L_1=\left\{a^m b^m c^{m+n} \mid m, n \geq 1\right\}...

Consider the following context-free grammar $G$, where $S, A$, and $B$ are the variables (nonterminals), $a$ and $b$ are the terminal symbols, $S$ is the start variable, and the ru...

A regular language $L$ is accepted by a non-deterministic finite automaton (NFA) with $n$ states. Which of the following statement(s) is/are FALSE?

Let L 1 be the language represented by the regular expression b * ab * (ab * ab * ) * and L 2 = { w ∈ (a + b) * | |w| ≤ 4 } , where |w| denotes the length of string w . The number...

Let G = (V, Σ, S, P) be a context-free grammar in Chomsky Normal Form with Σ = { a, b, c } and V containing 10 variable symbols including the start symbol S . The string w = a 30 b...

Consider the following two regular expressions over the alphabet {0,1} : $$r = 0^* + 1^*$$ $$s = 01^* + 10^*$$ The total number of strings of length less than or equal to 5, which...

Consider a context-free grammar $G$ with the following 3 rules. $S \rightarrow aS, \ S \rightarrow aSbS, S \rightarrow c$ Let $w \in L(G)$. Let $n_a(w)$, $n_b(w)$, $n_c(w)$ denote...

Let $L_1, L_2$ be two regular languages and $L_3$ a language which is not regular. Which of the following statements is/are always TRUE?

Consider the context-free grammar G below $$\matrix{ S & \to & {aSb|X} \cr X & \to & {aX|Xb|a|b,} \cr } $$ where S and X are non-terminals, and a and b are terminal symbols. The st...

Which of the following statements is/are CORRECT?

Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: $$\mathrm{letter\to[A-Za-z]}$$ $$\mathrm{le...

Consider the language L over the alphabet {0, 1}, given below: $$L = \{ w \in {\{ 0,1\} ^ * }|w$$ does not contain three or more consecutive $$1's\} $$. The minimum number of state...

Consider the following languages: $$\eqalign{ & {L_1} = \{ ww|w \in \{ a,b\} *\} \cr & {L_2} = \{ {a^n}{b^n}{c^m}|m,\,n \ge 0\} \cr & {L_3} = \{ {a^m}{b^n}{c^n}|m,\,n \ge 0\} \cr}...

Which of the following is/are undecidable?

Consider the following languages: L 1 = {a n wa n | w $$\in$$ {a, b}*} L 2 = {wxw R | w, x $$\in$$ {a, b}*, | w | , | x | > 0} Note that w R is the reversal of the string w. Which...

Which of the following statements is/are TRUE?

Let L ⊆ {0,1}* be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a minimal DFA with k s...

Suppose that L 1 is a regular and L 2 is a context-free language, Which one of the following languages is NOT necessarily context-free?

Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string ∈ divisible by three.

Let $$\left\langle M \right\rangle $$ denote an encoding of an automation M. Suppose that ∑ = {0, 1}. Which of the following languages is/are NOT recursive?

Let L 1 be a regular language and L 2 be a context-free language. Which of the following languages is/are context-free?

For a string w, we define w R to be the reverse of w. For example, if w = 01101 then w R = 10110. Which of the following languages is/are context-free?

Consider the following language. L = { w ∈ {0, 1}* | w ends with the substring 011} Which one of the following deterministic finite automata accepts L?

For a Turing machine M, {M} denotes an encoding of M. Consider the following two languages. L 1 = {(M) | M takes more than 2021 steps on all inputs} L 2 = {(M) | M takes more than...

Consider a network using the pure ALOHA medium access control protocol, where each frame is of length 1,000 bits. The channel transmission rate is 1 Mbps (= 10 6 bits per second)....

Consider the following two statements about regular languages: S 1 : Every infinite regular language contains an undecidable language as a subset. S 2 : Every finite language is re...

Consider the language L = { $${a^n}|n \ge 0$$ } $$ \cup $$ { $${a^n}{b^n}|n \ge 0$$ } and the following statements. I. L is deterministic context-free. II. L is context-free but no...

Consider the following statements. I. If L 1 $$ \cup $$ L 2 is regular, then both L 1 and L 2 must be regular. II. The class of regular languages is closed under infinite union. Wh...

Consider the following languages. L 1 = {wxyx | w, x, y ∈ (0 + 1) + } L 2 = {xy | x, y ∈ (a + b)*, |x| = |y|, x ≠ y} Which one of the following is TRUE?

Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?

Consider the following language. L = {x $$ \in $$ {a, b}* | number of a’s in x is divisible by 2 but not divisible by 3} The minimum number of states in a DFA that accepts L is ___...

Which of the following languages are undecidable? Note that $$\langle M\rangle $$ indicates encoding of the Turing machine M. L 1 = $$\left\{ {\langle M\rangle |L\left( M \right) =...

Consider the following sets : S1. Set of all recursively enumerable languages over the alphabet $\{0,1\}$ S2. Set of all syntactically valid C programs S3. Set of all languages ove...

If L is a regular language over Σ = {a, b}, which one of the following languages is NOT regular?

Let $\Sigma$ be the set of all bijections from $\{1, \ldots, 5\}$ to $\{1, \ldots, 5\}$, where id denotes the identity function, i.e. $\operatorname{id}(j)=j, \forall j$. Let $\cir...

For Σ = {a, b}, let us consider the regular language L = {x | x = a 2+3k or x = b 10+12k , k ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by th...

Which one of the following languages over $\Sigma=\{a, b\}$ is NOT context-free?

Consider the following languages: $$\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,$$ $$\left\{ {{a^m}{b^n}{c^p}{d^q}} \right.|m + p = n + q,$$ where $$\left. {m,n,p,q \ge 0} \right\}$$ $$\...

The set of all recursively enumerable languages is

Consider the following problems. $$L(G)$$ denotes the language generated by a grammar $$G.$$ $$L(M)$$ denotes the language accepted by a machine $$M.$$ $$\,\,\,\,\,\,\,\,{\rm I}.\,...

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?

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} $$$ Wh...

Consider the following languages. $$\,\,\,\,\,\,\,\,\,\,\,\,$$ $${L_1} = \left\{ {\left\langle M \right\rangle |M} \right.$$ takes at least $$2016$$ steps on some input $$\left. \,...

Which of the following languages is generated by the given grammar? $$$S \to aS|bS|\varepsilon $$$

The number of states in the minimum sized $$DFA$$ that accepts the language defined by the regular expression $$${\left( {0 + 1} \right)^ * }\left( {0 + 1} \right){\left( {0 + 1} \...

Which of the following decision problems are undecidable? $$\,\,\,\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,\,\,\,\,\,$$ Given $$NFAs$$ $${N_1}$$ and $${N_2},$$ is $$L\left( {{N_1}} \right)...

Consider the following two statements : $$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,$$ If all states of an $$NFA$$ are accepting states then the language accepted by the $$\,\,\,\,\,\,\,\,\,...

Consider the following context-free grammars: $$\eqalign{ & {G_1}:\,\,\,\,\,S \to aS|B,\,\,B \to b|bB \cr & {G_2}:\,\,\,\,\,S \to aA|bB,\,\,A \to aA|B|\varepsilon ,\,\,B \to bB|\va...

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive $$0s$$ and two consecutive $$1s?$$

Consider the following types of languages: $${L_1}:$$ Regular, $${L_2}:$$ Context-free, $${L_3}:$$ Recursive, $${L_4}:$$ Recursively enumerable. Which of the following is/are TRUE...

Language $${L_1}$$ is defined by the grammar: $$S{}_1 \to a{S_1}b|\varepsilon $$ Language $${L_2}$$ is defined by the grammar: $$S{}_2 \to ab{S_2}|\varepsilon $$ Consider the follo...

Let $$X$$ be a recursive language and $$Y$$ be a recursively enumerable but not recursive language. Let $$W$$ and $$Z$$ be two languages such that $$\overline Y $$ reduces to $$W,$...

The number of states in the minimal deterministic finite automaton corresponding to the regular expression $${\left( {0 + 1} \right)^{\,\, * }}\left( {10} \right)$$ is ____________...

Language $${L_1}$$ is polynomial time reducible to language $${L_2}$$ . Language $${L_3}$$ is polynomial time reducible to $${L_2}$$ , which in turn is polynomial time reducible to...

Consider the alphabet $$\sum { = \left\{ {0,1} \right\},} $$ the null/empty string $$\lambda $$ and the sets of strings $${X_0},\,{X_1},$$ and $${X_2}$$ generated by the correspond...

Consider the following statements. $$\,\,\,$$ $${\rm I}.\,\,\,\,\,\,\,\,\,$$ The complement of every Turing decidable language is Turing decidable $$\,$$ $${\rm II}.\,\,\,\,\,\,\,\...

For any two languages L 1 and L 2 such that L 1 is context-free and L 2 is recursively enumerable but not recursive, which of the following is/are necessarily true? I. $${\overline...

Which of the following languages is/are regular? $${L_1}:\left\{ {wx{w^R}|w,x\, \in \left\{ {a,b} \right\}{}^ * } \right.$$ and $$\left. {\left| w \right|,\left| x \right| > 0} \ri...

Which of the following languages are context-free? $$$\eqalign{ & {L_1} = \left\{ {{a^m}{b^n}{a^n}{b^m}|m,n \ge 1} \right\} \cr & {L_2} = \left\{ {{a^m}{b^n}{a^m}{b^n}|m,n \ge 1} \...

Let $$L$$ be the language represented by the regular expression $$\sum {^ * 0011\sum {^ * } } $$ where $$\sum { = \left\{ {0,1} \right\}} .$$ What is the minimum number of states i...

Which one of the following is TRUE?

Let $$ < M > $$ be the encoding of a Turing machine as a string over $$\sum { = \left\{ {0,1} \right\}.} $$ Let $$L = \left\{ { < M > \left| M \right.} \right.$$ is a Turing machin...

Let $$A\,\,{ \le _m}\,\,B$$ denotes that language $$A$$ is mapping reducible (also known as many-to-one reducible) to language $$B.$$ Which one of the following is FALSE?

Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(110)'s$$ as $$(011)'s$$$$\left. \, \right\}$$. Let $${L_...

Which one of the following problems is un-decidable?