Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Search results for theory-of-computation
50
votes
5
answers
41
GATE CSE 2016 Set 2 | Question: 43
Consider the following languages: $L_{1}=\left\{a^{n}b^{m}c^{n+m}:m, n\geq 1\right\}$ $L_{2}=\left\{a^{n}b^{n}c^{2n} :n\geq 1\right\}$ Which one of the following is TRUE? Both $L_{1}$ and $L_{2}$ are context-free. $L_{1}$ is context ... $L_{2}$ is context-free while $L_{1}$ is not context-free. Neither $L_{1}$ nor $L_{2}$ is context-free.
Consider the following languages:$L_{1}=\left\{a^{n}b^{m}c^{n+m}:m, n\geq 1\right\}$$L_{2}=\left\{a^{n}b^{n}c^{2n} :n\geq 1\right\}$Which one of the following is TRUE?Bot...
Akash Kanase
21.5k
views
Akash Kanase
asked
Feb 12, 2016
Theory of Computation
gatecse-2016-set2
theory-of-computation
context-free-language
normal
+
–
44
votes
6
answers
42
GATE CSE 2017 Set 1 | Question: 34
If $G$ is a grammar with productions $S\rightarrow SaS\mid aSb\mid bSa\mid SS\mid\epsilon$ where $S$ is the start variable, then which one of the following strings is not generated by $G$? $abab$ $aaab$ $abbaa$ $babba$
If $G$ is a grammar with productions$S\rightarrow SaS\mid aSb\mid bSa\mid SS\mid\epsilon$where $S$ is the start variable, then which one of the following strings is not g...
Arjun
11.6k
views
Arjun
asked
Feb 14, 2017
Theory of Computation
gatecse-2017-set1
theory-of-computation
context-free-language
normal
+
–
78
votes
4
answers
43
GATE CSE 2018 | Question: 52
Given a language $L$, define $L^i$ as follows:$L^0 = \{ \varepsilon \}$$L^i = L^{i-1} \bullet L \text{ 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. The order of $L_1$ is ________.
Given a language $L$, define $L^i$ as follows:$$L^0 = \{ \varepsilon \}$$$$L^i = L^{i-1} \bullet L \text{ for all } I >0$$The order of a language $L$ is defined as the s...
gatecse
20.7k
views
gatecse
asked
Feb 14, 2018
Theory of Computation
gatecse-2018
theory-of-computation
numerical-answers
regular-language
2-marks
+
–
22
votes
3
answers
44
GATE CSE 1987 | Question: 1-xii
A context-free grammar is ambiguous if: The grammar contains useless non-terminals. It produces more than one parse tree for some sentence. Some production has two non terminals side by side on the right-hand side. None of the above.
A context-free grammar is ambiguous if:The grammar contains useless non-terminals.It produces more than one parse tree for some sentence.Some production has two non termi...
makhdoom ghaya
12.6k
views
makhdoom ghaya
asked
Nov 8, 2016
Theory of Computation
gate1987
theory-of-computation
context-free-language
ambiguous-grammar
+
–
32
votes
8
answers
45
GATE CSE 1989 | Question: 3-ii
Context-free languages and regular languages are both closed under the operation (s) of : Union Intersection Concatenation Complementation
Context-free languages and regular languages are both closed under the operation (s) of :UnionIntersectionConcatenationComplementation
makhdoom ghaya
12.0k
views
makhdoom ghaya
asked
Nov 27, 2016
Theory of Computation
gate1989
easy
theory-of-computation
closure-property
multiple-selects
+
–
42
votes
8
answers
46
GATE CSE 1992 | Question: 02,xvii
Which of the following regular expression identities is/are TRUE? $r^{(^\ast)} =r^\ast$ $(r^\ast s^\ast)=(r+s)^\ast$ $(r+s)^\ast = r^\ast + s^\ast$ $r^\ast s^\ast = r^\ast+s^\ast$
Which of the following regular expression identities is/are TRUE?$r^{(^\ast)} =r^\ast$$(r^\ast s^\ast)=(r+s)^\ast$$(r+s)^\ast = r^\ast + s^\ast$$r^\ast s^\ast = r^\ast+s^...
Kathleen
14.6k
views
Kathleen
asked
Sep 13, 2014
Theory of Computation
gate1992
theory-of-computation
regular-expression
easy
multiple-selects
+
–
33
votes
11
answers
47
GATE CSE 2017 Set 2 | Question: 16
Identify the language generated by the following grammar, where $S$ is the start variable. $ S \rightarrow XY$ $ X \rightarrow aX \mid a$ $ Y \rightarrow aYb \mid \epsilon$ $\{a^mb^n \mid m \geq n, n > 0 \}$ $ \{ a^mb^n \mid m \geq n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n \geq 0 \}$ $\{a^mb^n \mid m > n, n > 0 \}$
Identify the language generated by the following grammar, where $S$ is the start variable.$ S \rightarrow XY$$ X \rightarrow aX \mid a$$ Y \rightarrow aYb \mid \epsilon$$...
khushtak
18.4k
views
khushtak
asked
Feb 14, 2017
Theory of Computation
gatecse-2017-set2
theory-of-computation
context-free-language
+
–
56
votes
6
answers
48
GATE IT 2008 | Question: 36
Consider the following two finite automata. $M_1$ accepts $L_1$ and $M_2$ accepts $L_2$. $M_1$ $M_2$ Which one of the following is TRUE? $L_1 = L_2$ $L_1 \subset L_2$ $L_1 \cap L_{2}^{C} = \varnothing $ $L_1 \cup L_2 \neq L_1$
Consider the following two finite automata. $M_1$ accepts $L_1$ and $M_2$ accepts $L_2$.$M_1$$M_2$ Which one of the following is TRUE?$L_1 = L_2$$L_1 \subset L_2$$L_1 \ca...
Ishrat Jahan
12.6k
views
Ishrat Jahan
asked
Oct 28, 2014
Theory of Computation
gateit-2008
theory-of-computation
finite-automata
normal
+
–
31
votes
7
answers
49
GATE CSE 2020 | Question: 26
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M. $L_1 = \{\left \langle M \right \rangle \mid L(M) = \varnothing \}$ ... $L_1$, $L_3$, and $L_4$ only $L_1$ and $L_3$ only $L_2$ and $L_3$ only $L_2$, $L_3$, and $L_4$ only
Which of the following languages are undecidable? Note that $\left \langle M \right \rangle$ indicates encoding of the Turing machine M.$L_1 = \{\left \langle M \right \r...
Arjun
14.6k
views
Arjun
asked
Feb 12, 2020
Theory of Computation
gatecse-2020
theory-of-computation
decidability
2-marks
+
–
65
votes
12
answers
50
GATE CSE 2015 Set 1 | Question: 52
Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.
Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.
makhdoom ghaya
17.3k
views
makhdoom ghaya
asked
Feb 13, 2015
Theory of Computation
gatecse-2015-set1
theory-of-computation
finite-automata
easy
numerical-answers
minimal-state-automata
+
–
4
votes
3
answers
51
GATE CSE 2023 | Question: 14
Which of the following statements is/are $\text{CORRECT}?$ The intersection of two regular languages is regular. The intersection of two context-free languages is context-free. The intersection of two recursive languages is recursive. The intersection of two recursively enumerable languages is recursively enumerable.
Which of the following statements is/are $\text{CORRECT}?$The intersection of two regular languages is regular.The intersection of two context-free languages is context-f...
admin
8.2k
views
admin
asked
Feb 15, 2023
Theory of Computation
gatecse-2023
theory-of-computation
identify-class-language
multiple-selects
1-mark
+
–
11
votes
4
answers
52
GATE CSE 2023 | Question: 4
Consider the Deterministic Finite-state Automaton ($\text{DFA}$) $\mathcal{A}$ shown below. The $\text{DFA}$ runs on the alphabet $\{0,1\}$, and has the set of states $\{s, p, q, r\}$, with $s$ being the start state and $p$ being the only final state. Which one of the following ... $1\left(0^{*} 11\right)^{*}$ $0(0+1)^{*}$ $1(0+11)^{*}$ $1\left(110^{*}\right)^{*}$
Consider the Deterministic Finite-state Automaton ($\text{DFA}$) $\mathcal{A}$ shown below. The $\text{DFA}$ runs on the alphabet $\{0,1\}$, and has the set of states $\{...
admin
11.4k
views
admin
asked
Feb 15, 2023
Theory of Computation
gatecse-2023
theory-of-computation
regular-expression
1-mark
+
–
20
votes
2
answers
53
GATE CSE 2022 | Question: 38
Consider the following languages: $L_{1} = \{ ww | w \in \{a,b\}^{\ast} \}$ $L_{2} = \{a^{n} b^{n} c^{m} | m,n \geq 0 \}$ $L_{3} = \{a^{m} b^{n} c^{n} | m,n \geq 0 \}$ Which of the following statements is/are $\text{FALSE}?$ ... $L_{2}$ is context-free. $L_{2}, L_{3}$ and $L_{2} \cap L_{3}$ all are context-free. Neither $L_{1}$ nor its complement is context-free.
Consider the following languages:$L_{1} = \{ ww | w \in \{a,b\}^{\ast} \}$$L_{2} = \{a^{n} b^{n} c^{m} | m,n \geq 0 \}$$L_{3} = \{a^{m} b^{n} c^{n} | m,n \geq 0 \}$Which ...
Arjun
11.4k
views
Arjun
asked
Feb 15, 2022
Theory of Computation
gatecse-2022
theory-of-computation
context-free-language
multiple-selects
2-marks
+
–
40
votes
6
answers
54
GATE CSE 2013 | Question: 17
Which of the following statements is/are FALSE? For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. Turing recognizable languages are closed under union and complementation. Turing decidable languages are closed under intersection and ... and intersection. $1$ and $4$ only $1$ and $3$ only $2$ only $3$ only
Which of the following statements is/are FALSE?For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.Turing recognizable lan...
Arjun
21.0k
views
Arjun
asked
Sep 23, 2014
Theory of Computation
gatecse-2013
theory-of-computation
normal
closure-property
+
–
66
votes
4
answers
55
GATE CSE 2008 | Question: 51
Match the following: $\small{\begin{array}{|ll|ll|}\hline \text{E.} & \text{Checking that identifiers are declared before their use} & \text{P.} & \text{$L \: = \: \left\{a^nb^mc^nd^m \mid n\: \geq1, m \geq 1\right\}$} \\\hline \text{F.} & \text{Number of formal ... $\text{E-R, F-P, G-Q, H-S}$ $\text{E-P, F-R, G-S, H-Q}$
Match the following:$$\small{\begin{array}{|ll|ll|}\hline \text{E.} & \text{Checking that identifiers are declared before their use} & \text{P.} & \text{$L \: = \: \lef...
Kathleen
14.1k
views
Kathleen
asked
Sep 12, 2014
Theory of Computation
gatecse-2008
normal
theory-of-computation
grammar
match-the-following
+
–
38
votes
5
answers
56
GATE CSE 1997 | Question: 3.4
Given $\Sigma=\{a,b\}$, which one of the following sets is not countable? Set of all strings over $\Sigma$ Set of all languages over $\Sigma$ Set of all regular languages over $\Sigma$ Set of all languages over $\Sigma$ accepted by Turing machines
Given $\Sigma=\{a,b\}$, which one of the following sets is not countable?Set of all strings over $\Sigma$Set of all languages over $\Sigma$Set of all regular languages ov...
Kathleen
12.4k
views
Kathleen
asked
Sep 29, 2014
Theory of Computation
gate1997
theory-of-computation
normal
countable-uncountable-set
+
–
46
votes
7
answers
57
GATE CSE 2009 | Question: 41
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$. end with $0$. end with $00$. contain the substring $00$.
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$.end with $0$.end with $00$.contain the substring $00$.
Kathleen
21.2k
views
Kathleen
asked
Sep 22, 2014
Theory of Computation
gatecse-2009
theory-of-computation
finite-automata
easy
+
–
5
votes
1
answer
58
CONVERT CFG TO GNF
S→ AB A→ BS|b B→ SA|a INTO GNF
S→ ABA→ BS|bB→ SA|a INTO GNF
Menon Karthik
26.8k
views
Menon Karthik
asked
Dec 14, 2018
Theory of Computation
gnf
conjunctive-normal-form
theory-of-computation
context-free-language
+
–
1
votes
1
answer
59
GATE CSE 2024 | Set 1 | Question: 13
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? $L_1=L_2$ if and only if $L_1 \cap \overline{L_2}=\phi$ $L_1 \cup L_3$ is not regular $\overline{L_3}$ is not regular $\overline{L_1} \cup \overline{L_2}$ is regular
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?$L_1=L_2$ if and only if $L_1 \c...
Arjun
2.8k
views
Arjun
asked
Feb 16
Theory of Computation
gatecse2024-set1
multiple-selects
theory-of-computation
+
–
29
votes
9
answers
60
GATE CSE 1995 | Question: 1.9 , ISRO2017-13
In some programming language, an identifier is permitted to be a letter followed by any number of letters or digits. If $L$ and $D$ denote the sets of letters and digits respectively, which of the following expressions defines an identifier? $(L + D)^+$ $(L.D)^*$ $L(L + D)^*$ $L(L.D)^*$
In some programming language, an identifier is permitted to be a letter followed by any number of letters or digits. If $L$ and $D$ denote the sets of letters and digits ...
Kathleen
13.3k
views
Kathleen
asked
Oct 8, 2014
Theory of Computation
gate1995
theory-of-computation
regular-expression
easy
isro2017
+
–
Page:
« prev
1
2
3
4
5
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register