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
1
votes
0
answers
4351
Self study, preparation question, no source
How do I begin my GATE preparation to get in top 50 in GATE 2020 now? I'm a Mechanical Engineering student at an NIT, know basic coding but not the core subjects. Is there time left to read standard books? Is there someone on this platform who has actually done this?
How do I begin my GATE preparation to get in top 50 in GATE 2020 now? I'm a Mechanical Engineering student at an NIT, know basic coding but not the core subjects. Is ther...
Kedar S
925
views
Kedar S
asked
Apr 13, 2019
Written Exam
preparation
iisc
gate-preparation
iit
nit
reference-book
+
–
0
votes
0
answers
4352
Ullman (TOC) Edition 3 Exercise 8.3 Question 3 (Page No. 343)
Design a subroutine to move a TM head from its current position to the right, skipping overall $0's,$ until reaching a $1$ or a blank. If the current position does not hold $0,$ then the TM should halt. You may assume that there ... TM that accepts all strings of $0's$ and $1's$ that do not have two $1's$ in a row$.$
Design a subroutine to move a TM head from its current position to the right, skipping overall $0's,$ until reaching a $1$ or a blank. If the current position does not ho...
admin
610
views
admin
asked
Apr 13, 2019
Theory of Computation
ullman
theory-of-computation
turing-machine
descriptive
+
–
0
votes
0
answers
4353
Ullman (TOC) Edition 3 Exercise 8.3 Question 2 (Page No. 343)
A common operation in Turing-machine programs involves $"$shifting over$".$ Ideally, we would like to create an extra cell at the current head position, in which we could store some character. However, we cannot edit ... perform this operation. Hint $:$ Leave a special symbol to mark the position to which the head must return.
A common operation in Turing-machine programs involves $"$shifting over$".$ Ideally, we would like to create an extra cell at the current head position, in which we could...
admin
410
views
admin
asked
Apr 13, 2019
Theory of Computation
ullman
theory-of-computation
turing-machine
descriptive
+
–
0
votes
0
answers
4354
Ullman (TOC) Edition 3 Exercise 8.3 Question 1 (Page No. 343)
Design Turing machines for the following languages$:$ $\text{The set of strings with an equal number of 0's and 1's.}$ $\{a^{n}b^{n}c^{n}|n\geq 1\}.$ $\{ww^{R}|\text{w is any string of 0's and 1's\}}.$ Redesign your Turing machines from Exercise $8.2$ to take advantage of the programming techniques.
Design Turing machines for the following languages$:$$\text{The set of strings with an equal number of 0's and 1's.}$$\{a^{n}b^{n}c^{n}|n\geq 1\}.$$\{ww^{R}|\text{w is an...
admin
218
views
admin
asked
Apr 13, 2019
Theory of Computation
ullman
theory-of-computation
turing-machine
+
–
0
votes
0
answers
4355
Ullman (TOC) Edition 3 Exercise 8.2 Question 5 (Page No. 337)
Consider the Turing machine $M=(\{q_{0},q_{1},q_{2},q_{f}\},\{0,1\},\{0,1,B\},\delta,q_{0},B,\{q_{f}\})$ Informally but clearly describe the language $L(M)$ if $\delta$ consists of the following sets of rules$:$ ...
Consider the Turing machine$M=(\{q_{0},q_{1},q_{2},q_{f}\},\{0,1\},\{0,1,B\},\delta,q_{0},B,\{q_{f}\})$Informally but clearly describe the language $L(M)$ if $\delta$ con...
admin
284
views
admin
asked
Apr 13, 2019
Theory of Computation
ullman
theory-of-computation
turing-machine
+
–
0
votes
0
answers
4356
Ullman (TOC) Edition 3 Exercise 8.2 Question 4 (Page No. 336)
In this exercise we explore the equivalence between function computation and language recognition for Turing machines. For simplicity, we shall consider only functions from nonnegative integers to nonnegative integers, but the ideas of this problem ... $?$ If not, explain how you could modify the construction to make it work.
In this exercise we explore the equivalence between function computation and language recognition for Turing machines. For simplicity, we shall consider only functions fr...
admin
355
views
admin
asked
Apr 13, 2019
Theory of Computation
ullman
theory-of-computation
turing-machine
descriptive
+
–
0
votes
0
answers
4357
Ullman (TOC) Edition 3 Exercise 8.2 Question 3 (Page No. 336)
Design a Turing machine that takes as input a number $N$ and adds $1$ to it in binary. To be precise, the tape initially contains a $ \$ $ followed by $N$ in binary. The tape head is initially scanning the $ \$ $ in ... $ of your TM when given input $\$111.$
Design a Turing machine that takes as input a number $N$ and adds $1$ to it in binary. To be precise, the tape initially contains a $ \$ $ followed by $N$ in binary. The ...
admin
348
views
admin
asked
Apr 13, 2019
Theory of Computation
ullman
theory-of-computation
turing-machine
+
–
0
votes
0
answers
4358
Ullman (TOC) Edition 3 Exercise 8.2 Question 2 (Page No. 335 - 336)
Design Turing machines for the following languages$:$ $\text{The set of strings with an equal number of 0's and 1's.}$ $\{a^{n}b^{n}c^{n}|n\geq 1\}.$ $\{ww^{R}|\text{w is any string of 0's and 1's\}}.$
Design Turing machines for the following languages$:$$\text{The set of strings with an equal number of 0's and 1's.}$$\{a^{n}b^{n}c^{n}|n\geq 1\}.$$\{ww^{R}|\text{w is an...
admin
214
views
admin
asked
Apr 13, 2019
Theory of Computation
ullman
theory-of-computation
turing-machine
+
–
0
votes
0
answers
4359
Ullman (TOC) Edition 3 Exercise 8.2 Question 1 (Page No. 335)
Show the $ID's$ of the Turing machine of Fig.$8.9$ if the input tape contains$:$ $00$ $000111$ $00111$
Show the $ID's$ of the Turing machine of Fig.$8.9$ if the input tape contains$:$$00$$000111$$00111$
admin
486
views
admin
asked
Apr 13, 2019
Theory of Computation
ullman
theory-of-computation
turing-machine
+
–
1
votes
0
answers
4360
Made easy online test series toc
The no. Of state in minimal dfa for string starting with abb and ending with b over the alphabet a,b . Please construct dfa
The no. Of state in minimal dfa for string starting with abb and ending with b over the alphabet a,b .Please construct dfa
prashant dubey
4.6k
views
prashant dubey
asked
Apr 12, 2019
0
votes
0
answers
4361
Doubt on a gate question
https://gateoverflow.in/968/gate2003-85 How in the above question the functional dependency (date of birth -> age) is a partial functional dependency. (As told in the selected answer for this question) Because according to navathe the definition of partial functional dependency ... X and the dependency still holds; that is, for some A belongs to X (X - {A}) -> Y.
https://gateoverflow.in/968/gate2003-85How in the above question the functional dependency (date of birth - age) is a partial functional dependency. (As told in the selec...
Kushagra Chatterjee
366
views
Kushagra Chatterjee
asked
Apr 12, 2019
Databases
databases
+
–
0
votes
0
answers
4362
Peter Linz Edition 4 Exercise 4.3 Question 26 (Page No. 124)
Let $L=$ {$a^nb^m:n\geq100,m\leq50$}. (a) Can you use the pumping lemma to show that L is regular? (b) Can you use the pumping lemma to show that L is not regular? Explain your answers.
Let $L=$ {$a^nb^m:n\geq100,m\leq50$}.(a) Can you use the pumping lemma to show that L is regular?(b) Can you use the pumping lemma to show that L is not regular?Explain y...
Naveen Kumar 3
219
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
pumping-lemma
+
–
0
votes
0
answers
4363
Peter Linz Edition 4 Exercise 4.3 Question 25 (Page No. 124)
In the chain code language in Exercise 24, Section 3.1, let $L$ be the set of all $w ∈$ {$u,r,l,d$}$^*$ that describe rectangles. Show that $L$ is not a regular language.
In the chain code language in Exercise 24, Section 3.1, let $L$ be the set of all $w ∈$ {$u,r,l,d$}$^*$ that describe rectangles. Show that $L$ is not a regular languag...
Naveen Kumar 3
150
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
4364
Peter Linz Edition 4 Exercise 4.3 Question 22 (Page No. 124)
Consider the argument that the language associated with any generalized transition graph is regular. The language associated with such a graph is $L=\bigcup_{p∈P} L(r_p)$, where $P$ ... is regular. Show that in this case, because of the special nature of $P$, the infinite union is regular.
Consider the argument that the language associated with any generalized transition graph is regular. The language associated with such a graph is $L=\bigcu...
Naveen Kumar 3
187
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
closure-property
+
–
0
votes
0
answers
4365
Peter Linz Edition 4 Exercise 4.3 Question 21 (Page No. 124)
Let $P$ be an infinite but countable set, and associate with each $p ∈ P$ a language $L_p$. The smallest set containing every $L_p$ is the union over the infinite set $P$; it will be denoted by $U_{p∈p}L_p$. Show by example that the family of regular languages is not closed under infinite union.
Let $P$ be an infinite but countable set, and associate with each $p ∈ P$ a language $L_p$. The smallest set containing every $L_p$ is the union over the infinite set $...
Naveen Kumar 3
214
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
closure-property
+
–
0
votes
0
answers
4366
Peter Linz Edition 4 Exercise 4.3 Question 20 (Page No. 124)
Is the following language regular? $L=$ {$ww^Rv:v,w∈$ {$a,b$}$^+$}.
Is the following language regular? $L=$ {$ww^Rv:v,w∈$ {$a,b$}$^+$}.
Naveen Kumar 3
287
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
4367
Peter Linz Edition 4 Exercise 4.3 Question 19 (Page No. 124)
Are the following languages regular? (a) $L=$ {$uww^Rv:u,v,w∈ ${$a,b$}$^+$} (b) $L=$ {$uww^Rv:u,v,w∈ ${$a,b$}$^+$, $|u|\geq |v|$}
Are the following languages regular?(a) $L=$ {$uww^Rv:u,v,w∈ ${$a,b$}$^+$}(b) $L=$ {$uww^Rv:u,v,w∈ ${$a,b$}$^+$, $|u|\geq |v|$}
Naveen Kumar 3
152
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
4368
Peter Linz Edition 4 Exercise 4.3 Question 18 (Page No. 124)
Apply the pigeonhole argument directly to the language in $L=$ {$ww^R:w∈Σ^+$}.
Apply the pigeonhole argument directly to the language in $L=$ {$ww^R:w∈Σ^+$}.
Naveen Kumar 3
161
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
pigeonhole-principle
+
–
0
votes
0
answers
4369
Peter Linz Edition 4 Exercise 4.3 Question 17 (Page No. 124)
Let $L_1$ and $L_2$ be regular languages. Is the language $L =$ {$w : w ∈ L_1, w^R ∈ L_2$ necessarily regular?
Let $L_1$ and $L_2$ be regular languages. Is the language $L =$ {$w : w ∈ L_1, w^R ∈ L_2$ necessarily regular?
Naveen Kumar 3
114
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
1
votes
0
answers
4370
Peter Linz Edition 4 Exercise 4.3 Question 15 (Page No. 123)
Consider the languages below. For each, make a conjecture whether or not it is regular. Then prove your conjecture. (a) $L=$ {$a^nb^la^k:n+k+l \gt 5$} (b) $L=$ {$a^nb^la^k:n \gt 5,l> 3,k\leq l$} (c) $L=$ {$a^nb^l:n/l$ is an integer} (d) $L=$ ... $L=$ {$a^nb^l:n\geq 100,l\leq 100$} (g) $L=$ {$a^nb^l:|n-l|=2$}
Consider the languages below. For each, make a conjecture whether or not it is regular. Thenprove your conjecture.(a) $L=$ {$a^nb^la^k:n+k+l \gt 5$}(b) $L=$ {$a^nb^la^k:n...
Naveen Kumar 3
304
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
pumping-lemma
closure-property
+
–
0
votes
0
answers
4371
Made Easy Test Series :TOC1
$(a,b,c)$ represents by reading input $a$, it replaces $a$ by $b$ and moved to $c$ direction. Which of the following language accepted by TM? My question is what $y$ is accepting in TM? I mean why $y$ is needed? What language is accepted ?
$(a,b,c)$ represents by reading input $a$, it replaces $a$ by $b$ and moved to $c$ direction. Which of the following language accepted by TM?My question is what $y$ is ac...
srestha
239
views
srestha
asked
Apr 12, 2019
Theory of Computation
made-easy-test-series
automata
+
–
0
votes
0
answers
4372
How to find precedence?
Shubham_Kr
277
views
Shubham_Kr
asked
Apr 12, 2019
Compiler Design
made-easy-booklet
+
–
–1
votes
0
answers
4373
what is output
void fun(int,int*); int main() { int=-5,j=-2; fun(i,&j); print f(“i=%d j=%d\n”,i,j); return 0; } void fun(int i,int *j) { i=i*i; *j=*j * *j; }
void fun(int,int*);int main(){int=-5,j=-2;fun(i,&j);print f(“i=%d j=%d\n”,i,j);return 0;}void fun(int i,int *j){i=i*i;*j=*j * *j;}
altamash
363
views
altamash
asked
Apr 12, 2019
0
votes
0
answers
4374
linear programming
shruti gupta1
188
views
shruti gupta1
asked
Apr 12, 2019
1
votes
0
answers
4375
problem on back edge
Can someone provide good example to illustrate cross edge,back edge ,forward edge?
Can someone provide good example to illustrate cross edge,back edge ,forward edge?
Cristine
537
views
Cristine
asked
Apr 12, 2019
Algorithms
back-edge
+
–
2
votes
0
answers
4376
Peter Linz Edition 4 Exercise 4.3 Question 10 (Page No. 123)
Consider the language $L=$ {$a^n:n$ is not a perfect square}. (a) Show that this language is not regular by applying the pumping lemma directly. (b) Then show the same thing by using the closure properties of regular languages.
Consider the language $L=$ {$a^n:n$ is not a perfect square}.(a) Show that this language is not regular by applying the pumping lemma directly.(b) Then show the same thin...
Naveen Kumar 3
240
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
closure-property
+
–
1
votes
0
answers
4377
Peter Linz Edition 4 Exercise 4.3 Question 7 (Page No. 123)
Show that the language $L=$ {$a^nb^n:n\geq0$} $\cup$ {$a^nb^{n+1}:n\geq0$} $\cup$ {$a^nb^{n+2}:n\geq0$} is not regular.
Show that the language $L=$ {$a^nb^n:n\geq0$} $\cup$ {$a^nb^{n+1}:n\geq0$} $\cup$ {$a^nb^{n+2}:n\geq0$} is not regular.
Naveen Kumar 3
149
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
+
–
1
votes
0
answers
4378
Peter Linz Edition 4 Exercise 4.3 Question 5 (Page No. 122)
Determine whether or not the following languages on $Σ =$ {$a$} are regular. (a) $L =$ {$a^n: n ≥ 2,$ is a prime number}. (b) $L =$ {$a^n: n$ is not a prime number}. (c) $L =$ {$a^n: n = k^3$ for some $k ≥ 0$}. ( ... {$a^n: n$ is either prime or the product of two or more prime numbers}. (g) $L^*$, where $L$ is the language in part $(a)$.
Determine whether or not the following languages on $Σ =$ {$a$} are regular.(a) $L =$ {$a^n: n ≥ 2,$ is a prime number}.(b) $L =$ {$a^n: n$ is not a prime number}.(c) ...
Naveen Kumar 3
347
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
0
votes
0
answers
4379
Peter Linz Edition 4 Exercise 4.3 Question 4 (Page No. 122)
Prove that the following languages are not regular. (a) $L =$ {$a^nb^la^k : k ≥ n + l$}. (b) $L =$ {$a^nb^la^k : k ≠ n + l$}. (c) $L =$ {$a^nb^la^k: n = l$ or $l ≠ k$}. (d) $L =$ {$a^nb^l : n ≤ l$}. (e) $L =$ {$w: n_a (w) ≠ n_b (w)$ }. (f) $L =$ {$ww : w ∈${$a, b$}$^*$}. (g) $L =$ {$wwww^R : w ∈$ {$a, b$}$^*$}.
Prove that the following languages are not regular.(a) $L =$ {$a^nb^la^k : k ≥ n + l$}.(b) $L =$ {$a^nb^la^k : k ≠ n + l$}.(c) $L =$ {$a^nb^la^k: n = l$ or $l ≠ k$}...
Naveen Kumar 3
217
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
0
votes
0
answers
4380
Peter Linz Edition 4 Exercise 4.3 Question 2 (Page No. 122)
Prove the following generalization of the pumping lemma. If $L$ is regular, then there exists an $m$, such that the following holds for every sufficiently long $w ∈ L$ and every one of its decompositions $w = u_1υu_2$, with $u_1,u_2 ∈ Σ^*, |υ| \geq m.$ The ... $|xy| ≤ m, |y| ≥ 1,$ such that $u_1xy^izu_2 ∈ L$ for all $i = 0,1, 2, .$
Prove the following generalization of the pumping lemma.If $L$ is regular, then there exists an $m$, such that the following holds for every sufficiently long $w ∈ L$ a...
Naveen Kumar 3
137
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
+
–
Page:
« prev
1
...
141
142
143
144
145
146
147
148
149
150
151
...
590
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register