Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Search results for theory-of-computation
19
votes
3
answers
1
How to construct an automata with even number of a's and odd number of b's?
The alphabets are a and b. Construct a DFA
The alphabets are a and b.Construct a DFA
Gourab_Classic
109k
views
Gourab_Classic
asked
Mar 14, 2016
Theory of Computation
minimal-state-automata
theory-of-computation
finite-automata
combinatory
+
–
64
votes
8
answers
2
GATE CSE 1997 | Question: 6.4
Which one of the following regular expressions over $\{0,1\}$ denotes the set of all strings not containing $\text{100}$ as substring? $0^*(1+0)^*$ $0^*1010^*$ $0^*1^*01^*$ $0^*(10+1)^*$
Which one of the following regular expressions over $\{0,1\}$ denotes the set of all strings not containing $\text{100}$ as substring?$0^*(1+0)^*$$0^*1010^*$$0^*1^*01^*$$...
Kathleen
37.5k
views
Kathleen
asked
Sep 29, 2014
Theory of Computation
gate1997
theory-of-computation
regular-expression
normal
+
–
108
votes
7
answers
3
GATE CSE 2016 Set 2 | Question: 44
Consider the following languages. $L_{1} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2016 steps on some input} \right\}$ ... not recursive $L_{1}, L_{2}$ are recursive and $L_{3}$ is not recursive $L_{1}, L_{2}, L_{3}$ are recursive
Consider the following languages.$L_{1} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2016 steps on some input} \right\}$,$L_{2} = \left\{\left\langl...
Akash Kanase
33.6k
views
Akash Kanase
asked
Feb 12, 2016
Theory of Computation
gatecse-2016-set2
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
5
votes
4
answers
4
Difference between DPDA and NPDA?
Amit Sharma
38.9k
views
Amit Sharma
asked
Jun 1, 2016
Theory of Computation
theory-of-computation
pushdown-automata
+
–
77
votes
12
answers
5
GATE CSE 2017 Set 2 | Question: 39
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$ ... $\emptyset$ $\{q_0, q_1, q_3\}$ $\{q_0, q_1, q_2\}$ $\{q_0, q_2, q_3 \}$
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below:$$\...
Arjun
28.4k
views
Arjun
asked
Feb 14, 2017
Theory of Computation
gatecse-2017-set2
theory-of-computation
finite-automata
+
–
54
votes
15
answers
6
GATE CSE 2017 Set 1 | Question: 22
Consider the language $L$ given by the regular expression $(a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting $L$ is ___________ .
Consider the language $L$ given by the regular expression $(a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finite-...
Arjun
29.3k
views
Arjun
asked
Feb 14, 2017
Theory of Computation
gatecse-2017-set1
theory-of-computation
finite-automata
numerical-answers
minimal-state-automata
+
–
50
votes
6
answers
7
GATE CSE 2019 | Question: 15
For $\Sigma = \{a ,b \}$, let us consider the regular language $L=\{x \mid x = a^{2+3k} \text{ or } x=b^{10+12k}, k \geq 0\}$. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for $L$ ? $3$ $5$ $9$ $24$
For $\Sigma = \{a ,b \}$, let us consider the regular language $L=\{x \mid x = a^{2+3k} \text{ or } x=b^{10+12k}, k \geq 0\}$. Which one of the following can be a pumping...
Arjun
34.2k
views
Arjun
asked
Feb 7, 2019
Theory of Computation
gatecse-2019
theory-of-computation
pumping-lemma
1-mark
+
–
93
votes
8
answers
8
GATE CSE 2006 | Question: 34
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is:$3$$5$$8$$9$
Rucha Shelke
34.3k
views
Rucha Shelke
asked
Sep 22, 2014
Theory of Computation
gatecse-2006
theory-of-computation
finite-automata
normal
minimal-state-automata
+
–
59
votes
8
answers
9
GATE CSE 2016 Set 1 | Question: 42
Consider the following context-free grammars; $G_1 : S \to aS \mid B, B \to b \mid bB$ $G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$ ... $\{ a^mb^n \mid m > 0 \text{ or } n>0\}$
Consider the following context-free grammars;$G_1 : S \to aS \mid B, B \to b \mid bB$$G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon$W...
Sandeep Singh
26.8k
views
Sandeep Singh
asked
Feb 12, 2016
Theory of Computation
gatecse-2016-set1
theory-of-computation
context-free-language
normal
+
–
83
votes
4
answers
10
GATE CSE 2015 Set 1 | Question: 51
Consider the NPDA ... follows: Which one of the following sequences must follow the string $101100$ so that the overall string is accepted by the automaton? $10110$ $10010$ $01010$ $01001$
Consider the NPDA $$ \left \langle Q= \left \{ q_{0}, q_{1}, q_{2} \right \},\Sigma = \left \{ 0, 1 \right \}, \Gamma = \left \{ 0, 1, \perp \right \}, \delta, q_{0}, \p...
makhdoom ghaya
23.8k
views
makhdoom ghaya
asked
Feb 13, 2015
Theory of Computation
gatecse-2015-set1
theory-of-computation
pushdown-automata
normal
+
–
29
votes
7
answers
11
GATE CSE 2020 | Question: 10
Consider the language $L = \{a^{n}\mid n \geq 0\} \cup \{a^{n}b^{n}\mid n \geq 0\}$ and the following statements. $L$ is deterministic context-free. $L$ is context-free but not deterministic context-free. $L$ is not $LL(k)$ for any $k$. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Ⅰ and Ⅲ only Ⅲ only
Consider the language $L = \{a^{n}\mid n \geq 0\} \cup \{a^{n}b^{n}\mid n \geq 0\}$ and the following statements.$L$ is deterministic context-free.$L$ is context-free but...
Arjun
20.1k
views
Arjun
asked
Feb 12, 2020
Theory of Computation
gatecse-2020
theory-of-computation
identify-class-language
1-mark
+
–
33
votes
4
answers
12
GATE CSE 2020 | Question: 32
Consider the following languages. $\begin{array}{ll} L_1= \{ wxyx \mid w,x,y \in (0+1)^{+} \} \\ L_2= \{xy \mid x,y \in (a+b)^{*}, \mid x \mid=\mid y \mid, x \neq y \} \end{array}$ ... context- free but not regular and $L_2$ is context-free. Neither $L_1$ nor $L_2$ is context- free. $L_1$ context- free but $L_2$ is not context-free.
Consider the following languages.$$\begin{array}{ll} L_1= \{ wxyx \mid w,x,y \in (0+1)^{+} \} \\ L_2= \{xy \mid x,y \in (a+b)^{*}, \mid x \mid=\mid y \mid, x \neq y \} \e...
Arjun
18.1k
views
Arjun
asked
Feb 12, 2020
Theory of Computation
gatecse-2020
theory-of-computation
identify-class-language
2-marks
+
–
71
votes
14
answers
13
GATE CSE 2012 | Question: 12
What is the complement of the language accepted by the NFA shown below? Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string. $\phi$ $\{\epsilon\}$ $a^*$ $\{a , \epsilon\}$
What is the complement of the language accepted by the NFA shown below?Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string.$\phi$$\{\epsilon\}$$a^*$$\{a , \epsilon...
gatecse
19.3k
views
gatecse
asked
Aug 5, 2014
Theory of Computation
gatecse-2012
finite-automata
easy
theory-of-computation
+
–
54
votes
13
answers
14
GATE CSE 2015 Set 2 | Question: 35
Consider the alphabet $\Sigma = \{0, 1\}$, the null/empty string $\lambda$ and the set of strings $X_0, X_1, \text{ and } X_2$ generated by the corresponding non-terminals of a regular grammar. $X_0, X_1, \text{ and } X_2$ are related as follows. $X_0 = 1 X_1$ $X_1 = 0 X_1 + 1 X_2$ ... $10(0^*+(10)^*)1$ $10(0^*+(10)^*)^*1$ $1(0+10)^*1$ $10(0+10)^*1 +110(0+10)^*1$
Consider the alphabet $\Sigma = \{0, 1\}$, the null/empty string $\lambda$ and the set of strings $X_0, X_1, \text{ and } X_2$ generated by the corresponding non-terminal...
go_editor
18.9k
views
go_editor
asked
Feb 12, 2015
Theory of Computation
gatecse-2015-set2
theory-of-computation
regular-grammar
normal
+
–
117
votes
6
answers
15
GATE CSE 2014 Set 2 | Question: 36
Let $L_1=\{w\in\{0,1\}^*\mid w$ $\text{ has at least as many occurrences of }$ $(110)'\text{s as }$ $(011)'\text{s} \}$. Let $L_2=\{w \in\{0,1\}^*\ \mid w$ $ \text{ has at least as many occurrences of }$ ... is TRUE? $L_1$ is regular but not $L_2$ $L_2$ is regular but not $L_1$ Both $L_1$ and $L_2$ are regular Neither $L_1$ nor $L_2$ are regular
Let $L_1=\{w\in\{0,1\}^*\mid w$ $\text{ has at least as many occurrences of }$ $(110)'\text{s as }$ $(011)'\text{s} \}$. Let $L_2=\{w \in\{0,1\}^*\ \mid w$ $ \text{ has a...
go_editor
25.2k
views
go_editor
asked
Sep 28, 2014
Theory of Computation
gatecse-2014-set2
theory-of-computation
normal
regular-language
+
–
55
votes
9
answers
16
GATE IT 2004 | Question: 40
Let $M = (K, Σ, Г, Δ, s, F)$ be a pushdown automaton, where $K = (s, f), F = \{f\}, \Sigma = \{a, b\}, Г = \{a\}$ and $Δ = \{((s, a, \epsilon), (s, a)), ((s, b, \epsilon), (s, a)), (( s, a, a), (f, \epsilon)), ((f, a, a), (f, \epsilon)), ((f, b, a), (f, \epsilon))\}$. Which one of the following strings is not a member of $L(M)$? $aaa$ $aabab$ $baaba$ $bab$
Let $M = (K, Σ, Г, Δ, s, F)$ be a pushdown automaton, where$K = (s, f), F = \{f\}, \Sigma = \{a, b\}, Г = \{a\}$ and$Δ = \{((s, a, \epsilon), (s, a)), ((s, b, \epsil...
Ishrat Jahan
42.5k
views
Ishrat Jahan
asked
Nov 2, 2014
Theory of Computation
gateit-2004
theory-of-computation
pushdown-automata
normal
+
–
91
votes
5
answers
17
GATE CSE 2014 Set 2 | Question: 35
Let $\langle M \rangle$ be the encoding of a Turing machine as a string over $\Sigma=\left\{0,1\right\}$ ... $L$ is: decidable and recursively enumerable undecidable but recursively enumerable undecidable and not recursively enumerable decidable but not recursively enumerable
Let $\langle M \rangle$ be the encoding of a Turing machine as a string over $\Sigma=\left\{0,1\right\}$. Let $$L=\left\{\langle M \rangle \mid M \text{ is a Turing machi...
go_editor
27.8k
views
go_editor
asked
Sep 28, 2014
Theory of Computation
gatecse-2014-set2
theory-of-computation
turing-machine
normal
+
–
56
votes
12
answers
18
GATE CSE 2003 | Question: 14
The regular expression $0^*(10^*)^*$ denotes the same set as $(1^*0)^*1^*$ $0+(0+10)^*$ $(0+1)^*10(0+1)^*$ None of the above
The regular expression $0^*(10^*)^*$ denotes the same set as$(1^*0)^*1^*$$0+(0+10)^*$$(0+1)^*10(0+1)^*$None of the above
Kathleen
19.2k
views
Kathleen
asked
Sep 16, 2014
Theory of Computation
gatecse-2003
theory-of-computation
regular-expression
easy
+
–
57
votes
5
answers
19
GATE CSE 2019 | Question: 48
Let $\Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ denotes the identity function, i.e. $id(j)=j, \forall j$. Let $\circ$ ... Consider the language $L=\{x \in \Sigma^* \mid \pi (x) =id\}$. The minimum number of states in any DFA accepting $L$ is _______
Let $\Sigma$ be the set of all bijections from $\{1, \dots , 5\}$ to $\{1, \dots , 5 \}$, where $id$ denotes the identity function, i.e. $id(j)=j, \forall j$. Let $\circ$...
Arjun
20.3k
views
Arjun
asked
Feb 7, 2019
Theory of Computation
gatecse-2019
numerical-answers
theory-of-computation
finite-automata
minimal-state-automata
difficult
2-marks
+
–
74
votes
8
answers
20
GATE CSE 2017 Set 1 | Question: 10
Consider the following context-free grammar over the alphabet $\Sigma = \{a,b,c\}$ with $S$ as the start symbol:$S \rightarrow abScT \mid abcT$$T \rightarrow bT \mid b$ ... $\{\left ( ab \right )^{n}\left ( cb^{n} \right )^{m} \mid m,n \geq 1 \}$
Consider the following context-free grammar over the alphabet $\Sigma = \{a,b,c\}$ with $S$ as the start symbol:$$S \rightarrow abScT \mid abcT$$$$T \rightarrow bT \mid ...
Arjun
21.7k
views
Arjun
asked
Feb 14, 2017
Theory of Computation
gatecse-2017-set1
theory-of-computation
context-free-language
normal
+
–
Page:
1
2
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register