Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged peter-linz
1
votes
0
answers
301
Peter Linz Edition 5 Exercise 10.5 Question 4(d) (Page No. 275)
Find linear bounded automata for the following language. $L = \Big\{ww:w\in\{a,b\}^+\Big\}$.
Find linear bounded automata for the following language. $L = \Big\{ww:w\in\{a,b\}^+\Big\}$.
Rishi yadav
424
views
Rishi yadav
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
+
–
0
votes
0
answers
302
Peter Linz Edition 5 Exercise 10.5 Question 4(c) (Page No. 275)
Find linear bounded automata for the following language. $L = \{a^n: \text{n is not a prime number}\}$.
Find linear bounded automata for the following language. $L = \{a^n: \text{n is not a prime number}\}$.
Rishi yadav
251
views
Rishi yadav
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
proof
+
–
0
votes
0
answers
303
Peter Linz Edition 5 Exercise 10.5 Question 4(b) (Page No. 275)
Find linear bounded automata for the following language. $L = \{a^n: \text{n is a prime number}\}$.
Find linear bounded automata for the following language. $L = \{a^n: \text{n is a prime number}\}$.
Rishi yadav
256
views
Rishi yadav
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
+
–
0
votes
0
answers
304
Peter Linz Edition 5 Exercise 10.5 Question 4(a) (Page No. 275)
Find linear bounded automata for the following language. $L = \{a^n: n = m^2,m\geq 1\}$
Find linear bounded automata for the following language. $L = \{a^n: n = m^2,m\geq 1\}$
Rishi yadav
139
views
Rishi yadav
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
+
–
0
votes
0
answers
305
Peter Linz Edition 5 Exercise 10.5 Question 3 (Page No. 275)
Consider an offline Turing machine in which the input can be read only once, moving left to right, not rewritten. On its work tape, it can use at most n extra cells for work space, where n is fixed for all inputs. Show that such a machine is equivalent to a finite automaton.
Consider an offline Turing machine in which the input can be read only once, moving left to right, not rewritten. On its work tape, it can use at most n extra cells for w...
Rishi yadav
263
views
Rishi yadav
asked
Apr 3, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
proof
+
–
2
votes
1
answer
306
Peter Linz Edition 4 Exercise 3.2 Question 10 (Page No. 88)
Find regular expressions for the languages accepted by the following automata:- https://gateoverflow.in/304714/peter-linz-edition-4-exercise-3-2-question-10-b-page-no-88
Find regular expressions for the languages accepted by the following automata:-https://gateoverflow.in/304714/peter-linz-edition-4-exercise-3-2-question-10-b-page-no-88
Naveen Kumar 3
1.3k
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
regular-language
+
–
0
votes
1
answer
307
Peter Linz Edition 4 Exercise 3.2 Question 9 (Page No. 88)
What language is accepted by the following generalized transition graph?
What language is accepted by the following generalized transition graph?
Naveen Kumar 3
617
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition4
regular-language
regular-expression
+
–
1
votes
0
answers
308
Peter Linz Edition 4 Exercise 3.2 Question 8 (Page No. 87)
Consider the following generalized transition graph. (a) Find an equivalent generalized transition graph with only two states. (b) What is the language accepted by this graph?
Consider the following generalized transition graph.(a) Find an equivalent generalized transition graph with only two states.(b) What is the language accepted by this gra...
Naveen Kumar 3
689
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
regular-language
+
–
0
votes
0
answers
309
Peter Linz Edition 4 Exercise 3.2 Question 7 (Page No. 87)
Find the minimal dfa that accepts $L(a^*bb) ∪ L(ab^*ba)$.
Find the minimal dfa that accepts $L(a^*bb) ∪ L(ab^*ba)$.
Naveen Kumar 3
152
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
regular-expression
+
–
1
votes
0
answers
310
Peter Linz Edition 4 Exercise 3.2 Question 6 (Page No. 87)
Find an nfa for all strings not containing the substring 101. Use this to derive a regular expression for that language.
Find an nfa for all strings not containing the substring 101. Use this to derive a regular expression for that language.
Naveen Kumar 3
217
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
regular-expression
+
–
0
votes
1
answer
311
Peter Linz Edition 4 Exercise 3.2 Question 5 (Page No. 87)
Find dfa's that accept the following languages. (a) $L = L (ab^*a^*)∪ L ((ab)^* ba)$. (b) $L = L (ab^*a^*) $ $\cap$ $L ((ab)^* ba)$.
Find dfa's that accept the following languages.(a) $L = L (ab^*a^*)∪ L ((ab)^* ba)$.(b) $L = L (ab^*a^*) $ $\cap$ $L ((ab)^* ba)$.
Naveen Kumar 3
292
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
regular-expression
+
–
0
votes
0
answers
312
Peter Linz Edition 4 Exercise 3.2 Question 4 (Page No. 87)
Find dfa's that accept the following languages. (a) $L (aa^* + aba^*b^*)$. (b) $L (ab (a + ab)^* (a + aa))$. (c) $L ((abab)^* + (aaa^* + b)^*)$. (d) $L (((aa^*)^* b)^*)$.
Find dfa's that accept the following languages.(a) $L (aa^* + aba^*b^*)$.(b) $L (ab (a + ab)^* (a + aa))$.(c) $L ((abab)^* + (aaa^* + b)^*)$.(d) $L (((aa^*)^* b)^*)$.
Naveen Kumar 3
238
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
regular-language
+
–
0
votes
0
answers
313
Peter Linz Edition 4 Exercise 3.2 Question 3 (Page No. 87)
Give an nfa that accepts the language $L((a + b)^* b(a + bb)^*)$.
Give an nfa that accepts the language $L((a + b)^* b(a + bb)^*)$.
Naveen Kumar 3
205
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
regular-language
+
–
0
votes
0
answers
314
Peter Linz Edition 4 Exercise 3.2 Question 2 (Page No. 87)
Find an nfa that accepts the complement of the language in $L (ab^*aa + bba^*ab)$.
Find an nfa that accepts the complement of the language in $L (ab^*aa + bba^*ab)$.
Naveen Kumar 3
133
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
regular-language
+
–
0
votes
1
answer
315
Peter Linz Edition 4 Exercise 3.2 Question 1 (Page No. 87)
Find an nfa that accepts the language $L (ab^*aa + bba^*ab)$.
Find an nfa that accepts the language $L (ab^*aa + bba^*ab)$.
Naveen Kumar 3
163
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
regular-language
+
–
1
votes
0
answers
316
Peter Linz Edition 5 Exercise 10.5 Question 2 (Page No. 275)
$\text{Example: }$Find a linear bounded automaton that accepts the language $L = \{a^{n!}:n\geq0\}$ Find a solution for Example that does not require track as scratch space.
$\text{Example: }$Find a linear bounded automaton that accepts the language $L = \{a^{n!}:n\g...
Rishi yadav
166
views
Rishi yadav
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
+
–
0
votes
0
answers
317
Peter Linz Edition 5 Exercise 10.5 Question 1 (Page No. 275)
$\text{Example: }$Find a linear bounded automaton that accepts the language $L = \{a^{n!}:n\geq0\}$ Give details for the solution of Example.
$\text{Example: }$Find a linear bounded automaton that accepts the language $L = \{a^{n!}:n\g...
Rishi yadav
227
views
Rishi yadav
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
+
–
0
votes
0
answers
318
Peter Linz Edition 5 Exercise 10.4 Question 9 (Page No. 273)
Show that the Cartesian product of a finite number of countable sets is countable.
Show that the Cartesian product of a finite number of countable sets is countable.
Rishi yadav
127
views
Rishi yadav
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
proof
+
–
0
votes
0
answers
319
Peter Linz Edition 5 Exercise 10.4 Question 8 (Page No. 273)
Suppose that $S_1$ and $S_2$ are countable sets. Show that then $S_1\cup S_2$ and $S_1 \times S_2$ are also countable.
Suppose that $S_1$ and $S_2$ are countable sets. Show that then $S_1\cup S_2$ and $S_1 \times S_2$ are also countable.
Rishi yadav
123
views
Rishi yadav
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
proof
+
–
0
votes
0
answers
320
Peter Linz Edition 5 Exercise 10.4 Question 7 (Page No. 273)
Show that the set of all triplets, $(i,j,k)$ with $i,j,k$ positive integers, is countable,
Show that the set of all triplets, $(i,j,k)$ with $i,j,k$ positive integers, is countable,
Rishi yadav
175
views
Rishi yadav
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
proof
+
–
0
votes
0
answers
321
Peter Linz Edition 5 Exercise 10.4 Question 5 (Page No. 272)
Design a Turing machine that enumerates the following set in proper order $L = \{a^nb^n:n\geq 1\}$.
Design a Turing machine that enumerates the following set in proper order $L = \{a^nb^n:n\geq 1\}$...
Rishi yadav
166
views
Rishi yadav
asked
Apr 2, 2019
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition5
turing-machine
+
–
0
votes
0
answers
322
Peter Linz Edition 5 Exercise 10.4 Question 4 (Page No. 272)
$\text{Exercise 3:}$ Sketch a Turing machine program that enumerates the set {0,1}+{0,1}+ in proper order. $\text{Exercise 4:}$ What is the index of $0^i1^j$ in Exercise 3$?$
$\text{Exercise 3:}$ Sketch a Turing machine program that enumerates the set {0,1}+{0,1}+ in proper order.$\text{Exercise 4:}$ What is the index of $0^i1^j$ in Exercise 3...
Rishi yadav
174
views
Rishi yadav
asked
Apr 2, 2019
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition5
turing-machine
+
–
0
votes
0
answers
323
Peter Linz Edition 5 Exercise 10.4 Question 3 (Page No. 272)
Sketch a Turing machine program that enumerates the set $\{0,1\}^+$ in proper order.
Sketch a Turing machine program that enumerates the set $\{0,1\}^+$ in proper order.
Rishi yadav
127
views
Rishi yadav
asked
Apr 2, 2019
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition5
turing-machine
+
–
0
votes
0
answers
324
Peter Linz Edition 5 Exercise 10.4 Question 2 (Page No. 272)
Give a complete encoding, using the suggested method, for the Turing machine with $\delta(q_1,a_1) = (q_1,a_1,R)$, $\delta(q_1,a_2) = (q_3,a_1,L)$, $\delta(q_3,a_1) = (q_2,a_2,L)$,
Give a complete encoding, using the suggested method, for the Turing machine with $\delta(q_1,a_1) = (q_1,a_1,R)$...
Rishi yadav
134
views
Rishi yadav
asked
Apr 2, 2019
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition5
turing-machine
+
–
0
votes
0
answers
325
Peter Linz Edition 5 Exercise 10.4 Question 1 (Page No. 272)
Sketch an algorithm that examines a string in $\{0,1\}^+$ to determine whether or not it represents an encoded Turing machine.
Sketch an algorithm that examines a string in $\{0,1\}^+$ to determine whether or not it represents an encoded Turing machine.
Rishi yadav
188
views
Rishi yadav
asked
Apr 2, 2019
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition5
turing-machine
+
–
0
votes
0
answers
326
Peter Linz Edition 5 Exercise 10.3 Question 7 (Page No. 268)
$\text{Definition:}$ A $\text{nondeterministic pushdown acceptor (npda)}$ is defined by the septuple $M = (Q,\Sigma,\Gamma,\delta,q_0,z,F)$ where $Q$ ... being pushed on these two stacks. Show that the class of two-stack automata is equivalent to the class of Turing machines.
$\text{Definition:}$ A $\text{nondeterministic pushdown acceptor (npda)}$ is defined by the septuple $M = (Q,\Sigm...
Rishi yadav
188
views
Rishi yadav
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
proof
+
–
0
votes
0
answers
327
Peter Linz Edition 5 Exercise 10.3 Question 6 (Page No. 268)
Design a nondeterministic Turing machine that accepts the language. $L = \{a^n: \text{n is not a prime number}\}$.
Design a nondeterministic Turing machine that accepts the language. $L = \{a^n: \text{n is not a prime number}\}$...
Rishi yadav
285
views
Rishi yadav
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
+
–
0
votes
0
answers
328
Peter Linz Edition 5 Exercise 10.3 Question 5 (Page No. 268)
Write a simple program for a nondeterministic Turing machine that accepts the language $L = \Big\{ xww^Ry:x,y,w\in\{a,b\}^+,|x|\geq |y|\Big\}$. How would you solve this problem deterministically$?$
Write a simple program for a nondeterministic Turing machine that accepts the language $L = \Big\{ xww^Ry:x,y,w\in\{a,b\...
Rishi yadav
113
views
Rishi yadav
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
+
–
0
votes
1
answer
329
Peter Linz Edition 4 Exercise 3.1 Question 26 (Page No. 77)
Find an nfa that accepts the language $L (aa^* (a + b))$.
Find an nfa that accepts the language $L (aa^* (a + b))$.
Naveen Kumar 3
274
views
Naveen Kumar 3
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-expression
finite-automata
+
–
0
votes
0
answers
330
Peter Linz Edition 5 Exercise 10.3 Question 4 (Page No. 268)
Outline how one would write a program for a nondeterministic Turing machine to accept the language $L=\{ww^Rw:w\in\{a,b\}^+\}$.
Outline how one would write a program for a nondeterministic Turing machine to accept the language $L=\{ww^Rw...
Rishi yadav
136
views
Rishi yadav
asked
Apr 2, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
turing-machine
+
–
Page:
« prev
1
...
6
7
8
9
10
11
12
13
14
15
16
...
20
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register