Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Filter
No answer
No selected answer
No upvoted answer
Previous GATE
Featured
Recent questions without answers
0
votes
0
answers
4201
Michael Sipser Edition 3 Exercise 1 Question 39 (Page No. 89)
The construction in $\text{Theorem 1.54}$ shows that every $\text{GNFA}$ is equivalent to a $\text{GNFA}$ with only two states$.$ We can show that an opposite phenomenon occurs for $\text{DFAs.}$ Prove that for every $k > 1,$ a ... exists that is recognized by a $\text{DFA}$ with $k$ states but not by one with only $k − 1$ states$.$
The construction in $\text{Theorem 1.54}$ shows that every $\text{GNFA}$ is equivalent to a $\text{GNFA}$ with only two states$.$ We can show that an opposite phenomenon ...
admin
365
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
proof
+
–
0
votes
0
answers
4202
Michael Sipser Edition 3 Exercise 1 Question 35 (Page No. 89)
Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}\end{Bmatrix}.$ Here $\sum_{2}$ contains all columns of $0's$ ... $ is the reverse of the top row of $w$}\}.$ Show that $E$ is not regular$.$
Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}...
admin
176
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
0
votes
0
answers
4203
Michael Sipser Edition 3 Exercise 1 Question 34 (Page No. 89)
Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}\end{Bmatrix}.$ Here $\sum_{2}$ contains all columns of ... $\begin{bmatrix} 0\\0 \end{bmatrix}\notin D$ Show that $D$ is regular$.$
Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}...
admin
228
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
0
votes
0
answers
4204
Michael Sipser Edition 3 Exercise 1 Question 33 (Page No. 89)
Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}\end{Bmatrix}.$ Here $\sum_{2}$ contains all columns ... $C$ is regular. $\text{(You may assume the result claimed in question $31$})$
Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}...
admin
252
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
1
votes
0
answers
4205
Michael Sipser Edition 3 Exercise 1 Question 32 (Page No. 88)
Let $\sum_{3}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \\0 \end{bmatrix},\begin{bmatrix} 0\\0 \\1 \end{bmatrix},\begin{bmatrix} 0\\1 \\0 \end{bmatrix}, .,\begin{bmatrix} 1\\1 \\1 \end{bmatrix}\end{Bmatrix}.$ $\sum_{3}$ ... $B$ is regular. $\text{(Hint$:$Working with $B^{R}$ is easier. You may assume the result claimed in question $31$})$
Let $\sum_{3}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \\0 \end{bmatrix},\begin{bmatrix} 0\\0 \\1 \end{bmatrix},\begin{bmatrix} 0\\1 \\0 \end{bmatrix},…….,\begin{bmatrix} ...
admin
483
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
0
votes
0
answers
4206
Michael Sipser Edition 3 Exercise 1 Question 31 (Page No. 88)
For any string $w = w_{1}w_{2} · · · w_{n},$ the reverse of $w,$ written $w^{R},$ is the string $w$ in reverse order$, w_{n} · · · w_{2}w_{1}.$ For any language $A,$ let $A^{R} = \{w^{R}| w\in A\}.$ Show that if $A$ is regular$,$ so is $A^{R}.$
For any string $w = w_{1}w_{2} · · · w_{n},$ the reverse of $w,$ written $w^{R},$ is the string $w$ in reverse order$, w_{n} · · · w_{2}w_{1}.$ For any language $A,...
admin
307
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
0
votes
0
answers
4207
CSIR UGC NET
Let $A$ be a $3 \times 3$ real matrix. Suppose 1 and -1 are two of the three Eigen values of $A$ and 18 is one of the Eigen values of $A^2+3 A$. Then Both $A$ and $A^2+3 A$ are invertible $A^2+3 A$ is invertible but $A$ is not invertible $A$ is invertible but $A^2+3 A$ is not invertible Both $\mathrm{A}$ and $A^2+3 A$ are not invertible.
Let $A$ be a $3 \times 3$ real matrix. Suppose 1 and -1 are two of the three Eigen values of $A$ and 18 is one of the Eigen values of $A^2+3 A$. ThenBoth $A$ and $A^2+3 A...
Hirak
548
views
Hirak
asked
Apr 28, 2019
Linear Algebra
linear-algebra
eigen-value
matrix
+
–
0
votes
0
answers
4208
Ford-Fulkersons method:
Nandkishor3939
432
views
Nandkishor3939
asked
Apr 28, 2019
Algorithms
algorithms
+
–
0
votes
0
answers
4209
Made Easy Engineering Maths book
The ans given is b, but i am not able to understande why. According to me the largest eigen value is 2, and therefore none of the option matches..!
The ans given is b, but i am not able to understande why. According to me the largest eigen value is 2, and therefore none of the option matches..!
Hirak
833
views
Hirak
asked
Apr 27, 2019
0
votes
0
answers
4210
POSET self doubt
What is dual of a POSET?
What is dual of a POSET?
aditi19
468
views
aditi19
asked
Apr 27, 2019
Set Theory & Algebra
lattice
self-doubt
set-theory&algebra
relations
partial-order
+
–
0
votes
0
answers
4211
Made Easy Test Series: Self Doubt
How bottom-up parser like Operator-Precedence parser parse some ambiguous grammar? According to stanford diagram , ambiguous grammar cannot be parsed and it is separate form of grammar Am I right?
How bottom-up parser like Operator-Precedence parser parse some ambiguous grammar?According to stanford diagram , ambiguous grammar cannot be parsed and it is separate fo...
srestha
286
views
srestha
asked
Apr 27, 2019
Compiler Design
compiler-design
parsing
descriptive
+
–
0
votes
0
answers
4212
IS THERE ANY other SITE FOR TEST SERIES SUBJECT WISE for NTA NET CS
hii guys there are lot of sites providing Q/A for ugcnet cs but not test series, some sites provide but not good quality they provide BANK,GATE,RAILWAYS IN TEST SERIES. I saw only one site Career Endeavour is good. IS THERE ANY other SITE FOR TEST SERIES SUBJECT WISE for NTA NET CS
hii guys there are lot of sites providing Q/A for ugcnet cs but not test series, some sites provide but not good quality they provide BANK,GATE,RAILWAYS IN TEST SERIES. I...
Adnan Ashraf
655
views
Adnan Ashraf
asked
Apr 27, 2019
CBSE/UGC NET
test-series
ugcnet
ntanet
+
–
0
votes
0
answers
4213
Self doubts DFA
The minimum no. of states required to construct DFA which can accept length of the string is devisable by 4 where input string is 0,1 Please also construct dfa
The minimum no. of states required to construct DFA which can accept length of the string is devisable by 4 where input string is 0,1Please also construct dfa
prashant dubey
255
views
prashant dubey
asked
Apr 27, 2019
1
votes
0
answers
4214
IITG MTech DataScience
Did anyone receive call letter from IITG Datascience for Written test, the shortlist was announced and it is informed that call letter will be sent by 26th apr 12PM...anyone have any info?
Did anyone receive call letter from IITG Datascience for Written test, the shortlist was announced and it is informed that call letter will be sent by 26th apr 12PM...any...
balchandar reddy san
1.2k
views
balchandar reddy san
asked
Apr 27, 2019
Written Exam
admissions
getting-to-iits
general
+
–
0
votes
0
answers
4215
#self doubt
Is it required to focus on space complexity for "GATE"?
Is it required to focus on space complexity for "GATE"?
Rishabh Baghel
143
views
Rishabh Baghel
asked
Apr 27, 2019
0
votes
0
answers
4216
turing machine self doubt a+b=c
Turing machine, language A = {a+b=c | a, b, c are sequences of 1's; |c| = |a| + |b|; |a| >= 0 and |b| > 0}.
Turing machine,language A = {a+b=c | a, b, c are sequences of 1's; |c| = |a| + |b|; |a| >= 0 and |b| 0}.
manisha11
262
views
manisha11
asked
Apr 27, 2019
Theory of Computation
theory-of-computation
self-doubt
+
–
0
votes
0
answers
4217
BITS HD Exam Slot Query
The exam date for ME CSE is on 15th and 26th may, the slot booking will open on 4th may. My query is that whether slots for ME CSE will be there on both the dates (15th & 26th may) or only on any one particular day?
The exam date for ME CSE is on 15th and 26th may, the slot booking will open on 4th may. My query is that whether slots for ME CSE will be there on both the dates (15th &...
balchandar reddy san
667
views
balchandar reddy san
asked
Apr 26, 2019
Written Exam
bits
bits-hd
+
–
1
votes
0
answers
4218
iit admissions
I have been shortlisted for Mtech iit Bhubaneshwar and most likely would be for iit Guwahati data science but on the day of written test i have BTech final year exam what should I do?
I have been shortlisted for Mtech iit Bhubaneshwar and most likely would be for iit Guwahati data science but on the day of written test i have BTech final year exam what...
yajush mishra
696
views
yajush mishra
asked
Apr 25, 2019
1
votes
0
answers
4219
regarding iit madras ms interview call
Does anyone know cutoff of iit madras for shortlisting for interview? My gate rank is 963 and my btech percentage is 76% but i didnt get call for interview
Does anyone know cutoff of iit madras for shortlisting for interview?My gate rank is 963 and my btech percentage is 76% but i didnt get call for interview
mradul
1.1k
views
mradul
asked
Apr 24, 2019
0
votes
0
answers
4220
Made Easy Test Series: TOC
The pushdown automata $M=\left \{ \left ( q_{0},q_{1},q_{2} \right ),\left ( a,b \right ) ,\left ( 0,1 \right ),\partial ,q_{0},0,\left \{ q_{0} \right \}\right \}$ $\partial \left ( q_{0},a,0 \right )=\left ( q_{1},10 \right )$ ... $q_{0}$ As last transition going from $q_{2}$ to $q_{0}$ and not $q_{0}$ to $q_{2}$ Am I right?
The pushdown automata $M=\left \{ \left ( q_{0},q_{1},q_{2} \right ),\left ( a,b \right ) ,\left ( 0,1 \right ),\partial ,q_{0},0,\left \{ q_{0} \right \}\right \}$$\part...
srestha
672
views
srestha
asked
Apr 23, 2019
Theory of Computation
theory-of-computation
made-easy-test-series
+
–
0
votes
0
answers
4221
Pgee mock exam
Dipanshu Rana
358
views
Dipanshu Rana
asked
Apr 23, 2019
7
votes
0
answers
4222
FAQ-3
How to utilize GO Book to get maximum benfit ?
How to utilize GO Book to get maximum benfit ?
Abhishek Shaw
564
views
Abhishek Shaw
asked
Apr 22, 2019
GATE
faq
+
–
0
votes
0
answers
4223
Self-Doubt(P-NP class)
$1)$ If the complement of NP-Complete problem is in NP, then can we also say , for this case complement of NP problem is in NP-Complete ? $2)$ If the complement of NP-Complete problem is in Co-NP, then can we also say, for this case complement of Co-NP problem is in NP-Complete?
$1)$ If the complement of NP-Complete problem is in NP, then can we also say , for this case complement of NP problem is in NP-Complete ?$2)$ If the complement of NP-Comp...
srestha
866
views
srestha
asked
Apr 22, 2019
Theory of Computation
p-np-npc-nph
theory-of-computation
+
–
0
votes
0
answers
4224
Michael Sipser Edition 3 Exercise 1 Question 26 (Page No. 87)
Using the solution you gave to question $25,$ give a formal description of the machines $T_{1}$ and $T_{2}$ depicted in question $24.$
Using the solution you gave to question $25,$ give a formal description of the machines $T_{1}$ and $T_{2}$ depicted in question $24.$
admin
615
views
admin
asked
Apr 21, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
fst
descriptive
+
–
0
votes
0
answers
4225
Decidability and Undecidability
From where to learn the decidability and Undecidability concept for gate? So that I can grasp the full concept of that topic crystal clear..(please suggest me except Shai Simonson..I had already watch that video but i could'nt clear my concepts from there) i am facing real difficulty on that topic
From where to learn the decidability and Undecidability concept for gate? So that I can grasp the full concept of that topic crystal clear..(please suggest me except Shai...
Ritabrata Dey
742
views
Ritabrata Dey
asked
Apr 21, 2019
Theory of Computation
theory-of-computation
+
–
0
votes
0
answers
4226
Michael Sipser Edition 3 Exercise 1 Question 23 (Page No. 87)
Let $B$ be any language over the alphabet $Σ.$ Prove that $B = B^{+}$ iff $BB ⊆ B.$
Let $B$ be any language over the alphabet $Σ.$ Prove that $B = B^{+}$ iff $BB ⊆ B.$
admin
531
views
admin
asked
Apr 21, 2019
Theory of Computation
michael-sipser
theory-of-computation
regular-language
proof
+
–
0
votes
0
answers
4227
Michael Sipser Edition 3 Exercise 1 Question 15 (Page No. 85)
Give a counterexample to show that the following construction fails to prove $\text{Theorem 1.49,}$ the closure of the class of regular languages under the star operation$.$ Let $N_{1} = (Q_1, Σ, δ_1, q_1, F_1)$ ... , $N1,$ for which the constructed automaton $N$ does not recognize the star of $N_{1}^{'s}$ language.
Give a counterexample to show that the following construction fails to prove $\text{Theorem 1.49,}$ the closure of the class of regular languages under the star operation...
admin
1.0k
views
admin
asked
Apr 21, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
0
votes
0
answers
4228
Michael Sipser Edition 3 Exercise 1 Question 14 (Page No. 85)
Show that if $M$ is a $DFA$ that recognizes language $B,$ swapping the accept and not accept states in $M$ yields a new $DFA$ recognizing the complement of $B.$ Conclude that the class of regular languages is closed under ... of $C.$ Is the class of languages recognized by $NFA's$ closed under complement$?$ Explain your answer$.$
Show that if $M$ is a $DFA$ that recognizes language $B,$ swapping the accept and not accept states in $M$ yields a new $DFA$ recognizing the complement of $B.$ Conclude ...
admin
893
views
admin
asked
Apr 21, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
+
–
1
votes
0
answers
4229
Michael Sipser Edition 3 Exercise 1 Question 13 (Page No. 85)
Let $F$ be the language of all strings over $\{0,1\}$ that do not contain a pair of $1's$ that are separated by an odd number of symbols. Give the state diagram of a $\text{DFA}$ with five states that recognizes $F.$ $($You may find it helpful first to find a $4$-state $\text{NFA}$ for the complement of $F.)$
Let $F$ be the language of all strings over $\{0,1\}$ that do not contain a pair of $1's$ that are separated by an odd number of symbols. Give the state diagram of a $\...
admin
1.3k
views
admin
asked
Apr 21, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
+
–
0
votes
0
answers
4230
Michael Sipser Edition 3 Exercise 1 Question 9 (Page No. 85)
Use the construction in the proof of $\text{Theorem 1.47}$ to give the state diagrams of $\text{NFA's}$ recognizing the concatenation of the languages described in and input alphabet is $\Sigma=\{0,1\}$ L1={w| the length of w is at ... L2={w| every odd position of w is a 1} L1={w| w contains at least three 1s} and L2=The empty set
Use the construction in the proof of $\text{Theorem 1.47}$ to give the state diagrams of $\text{NFA's}$ recognizing the concatenation of the languages described in and in...
admin
2.0k
views
admin
asked
Apr 21, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
state-diagram
+
–
Page:
« prev
1
...
136
137
138
139
140
141
142
143
144
145
146
...
590
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register