Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged michael-sipser
0
votes
0
answers
91
Michael Sipser Edition 3 Exercise 3 Question 3 (Page No. 187)
Modify the proof of Theorem $3.16$ to obtain Corollary $3.19$, showing that a language is decidable iff some nondeterministic Turing machine decides it. (You may assume the following theorem about trees. If every node in a ... many children and every branch of the tree has finitely many nodes, the tree itself has finitely many nodes.)
Modify the proof of Theorem $3.16$ to obtain Corollary $3.19$, showing that a language is decidable iff some nondeterministic Turing machine decides it. (You may assume t...
admin
487
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
non-determinism
turing-machine
descriptive
+
–
0
votes
0
answers
92
Michael Sipser Edition 3 Exercise 3 Question 2 (Page No. 187)
This exercise concerns $TM\: M_{1}$, whose description and state diagram appear in Example $3.9$. In each of the parts, give the sequence of configurations that $M_{1}$ enters when started on the indicated input string. $11$ $1\#1$ $1\#\#1$ $10\#11$ $10\#10$
This exercise concerns $TM\: M_{1}$, whose description and state diagram appear in Example $3.9$. In each of the parts, give the sequence of configurations that $M_{1}$ ...
admin
179
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
descriptive
+
–
0
votes
0
answers
93
Michael Sipser Edition 3 Exercise 3 Question 1 (Page No. 187)
This exercise concerns $TM\: M_{2}$, whose description and state diagram appear in Example $3.7$. In each of the parts, give the sequence of configurations that $M_{2}$ enters when started on the indicated input string. $0$ $00$ $000$ $000000$
This exercise concerns $TM\: M_{2}$, whose description and state diagram appear in Example $3.7$. In each of the parts, give the sequence of configurations that $M_{2}$ e...
admin
432
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
turing-machine
descriptive
+
–
0
votes
0
answers
94
Michael Sipser Edition 3 Exercise 2 Question 59 (Page No. 160)
If we disallow $\epsilon$-rules in CFGs, we can simplify the DK-test. In the simplified test,we only need to check that each of DK’s accept states has a single rule. Prove that a CFG without $\epsilon$-rules passes the simplified DK-test iff it is a DCFG.
If we disallow $\epsilon$-rules in CFGs, we can simplify the DK-test. In the simplified test,we only need to check that each of DK’s accept states has a single rule. Pr...
admin
297
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
descriptive
+
–
0
votes
0
answers
95
Michael Sipser Edition 3 Exercise 2 Question 58 (Page No. 160)
Let $C = \{ww^{R} \mid w in \{0,1\}^{\ast}\}$. Prove that $C$ is not a DCFL. (Hint: Suppose that when some DPDA $P$ is started in state $q$ with symbol $x$ on the top of its stack, $P$ never pops its ... of $P's$ stack at that point cannot affect its subsequent behavior, so $P's$ subsequent behavior can depend only on $q$ and $x$.)
Let $C = \{ww^{R} \mid w in \{0,1\}^{\ast}\}$. Prove that $C$ is not a DCFL. (Hint: Suppose that when some DPDA $P$ is started in state $q$ with symbol $x$ on the top of ...
admin
197
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
descriptive
+
–
2
votes
1
answer
96
Michael Sipser Edition 3 Exercise 2 Question 57 (Page No. 160)
Let $B = \{a^{i}b^{j}c^{k}\mid i,j,k \geq 0\: \text{and}\: i = j\: \text{or}\: i = k \}$. Prove that $B$ is not a DCFL.
Let $B = \{a^{i}b^{j}c^{k}\mid i,j,k \geq 0\: \text{and}\: i = j\: \text{or}\: i = k \}$. Prove that $B$ is not a DCFL.
admin
323
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
descriptive
+
–
0
votes
0
answers
97
Michael Sipser Edition 3 Exercise 2 Question 56 (Page No. 160)
Let $A = L(G_{1})$ where $G_{1}$ is defined in Question $2.55$. Show that $A$ is not a DCFL.(Hint: Assume that $A$ is a DCFL and consider its DPDA $P$. Modify $P$ ... an accept state, it pretends that $c's$ are $b's$ in the input from that point on. What language would the modified $P$ accept?)
Let $A = L(G_{1})$ where $G_{1}$ is defined in Question $2.55$. Show that $A$ is not a DCFL.(Hint: Assume that $A$ is a DCFL and consider its DPDA $P$. Modify $P$ so that...
admin
198
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
descriptive
+
–
1
votes
0
answers
98
Michael Sipser Edition 3 Exercise 2 Question 55 (Page No. 159)
Let $G_{1}$ be the following grammar that we introduced in Example $2.45$. Use the DK-test to show that $G_{1}$ is not a DCFG. $R \rightarrow S \mid T$ $S \rightarrow aSb \mid ab$ $T \rightarrow aTbb \mid abb$
Let $G_{1}$ be the following grammar that we introduced in Example $2.45$. Use the DK-test to show that $G_{1}$ is not a DCFG.$R \rightarrow S \mid T$$S \rightarrow aSb \...
admin
239
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
descriptive
+
–
0
votes
0
answers
99
Michael Sipser Edition 3 Exercise 2 Question 54 (Page No. 159)
Let G be the following grammar: $S \rightarrow T\dashv $ $T \rightarrow T aT b \mid T bT a | \epsilon$ Show that $L(G) = \{w\dashv \: \mid w\: \text{contains equal numbers of a’s and b’s} \}$. Use a proof by induction on the length of $w$. Use the DK-test to show that G is a DCFG. Describe a DPDA that recognizes L(G).
Let G be the following grammar:$S \rightarrow T\dashv $$T \rightarrow T aT b \mid T bT a | \epsilon$Show that $L(G) = \{w\dashv \: \mid w\: \text{contains equal numbers o...
admin
242
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
descriptive
+
–
0
votes
1
answer
100
Michael Sipser Edition 3 Exercise 2 Question 53 (Page No. 159)
Show that the class of DCFLs is not closed under the following operations: Union Intersection Concatenation Star Reversal
Show that the class of DCFLs is not closed under the following operations:UnionIntersectionConcatenationStarReversal
admin
320
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
closure-property
descriptive
+
–
0
votes
0
answers
101
Michael Sipser Edition 3 Exercise 2 Question 52 (Page No. 159)
Show that every DCFG generates a prefix-free language.
Show that every DCFG generates a prefix-free language.
admin
241
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
prefix-free-property
proof
+
–
0
votes
0
answers
102
Michael Sipser Edition 3 Exercise 2 Question 51 (Page No. 159)
Show that every DCFG is an unambiguous CFG.
Show that every DCFG is an unambiguous CFG.
admin
224
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
ambiguous
proof
+
–
0
votes
0
answers
103
Michael Sipser Edition 3 Exercise 2 Question 50 (Page No. 159)
We defined the $CUT$ of language $A$ to be $CUT(A) = \{yxz| xyz \in A\}$. Show that the class of $CFLs$ is not closed under $CUT$.
We defined the $CUT$ of language $A$ to be $CUT(A) = \{yxz| xyz \in A\}$. Show that the class of $CFLs$ is not closed under $CUT$.
admin
218
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
closure-property
descriptive
+
–
0
votes
1
answer
104
Michael Sipser Edition 3 Exercise 2 Question 49 (Page No. 159)
We defined the rotational closure of language $A$ to be $RC(A) = \{yx \mid xy \in A\}$.Show that the class of CFLs is closed under rotational closure.
We defined the rotational closure of language $A$ to be $RC(A) = \{yx \mid xy \in A\}$.Show that the class of CFLs is closed under rotational closure.
admin
1.3k
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
closure-property
descriptive
+
–
0
votes
0
answers
105
Michael Sipser Edition 3 Exercise 2 Question 48 (Page No. 159)
Let $\Sigma = \{0,1\}$. Let $C_{1}$ be the language of all strings that contain a $1$ in their middle third. Let $C_{2}$ be the language of all strings that contain two $1s$ ... $C_{1}$ is a CFL. Show that $C_{2}$ is not a CFL.
Let $\Sigma = \{0,1\}$. Let $C_{1}$ be the language of all strings that contain a $1$ in their middle third. Let $C_{2}$ be the language of all strings that contain two $...
admin
290
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
descriptive
+
–
1
votes
0
answers
106
Michael Sipser Edition 3 Exercise 2 Question 47 (Page No. 159)
Let $\Sigma = \{0,1\}$ and let $B$ be the collection of strings that contain at least one $1$ in their second half. In other words, $B = \{uv \mid u \in \Sigma^{\ast}, v \in \Sigma^{\ast}1\Sigma^{\ast}\: \text{and} \mid u \mid \geq \mid v \mid \}$. Give a PDA that recognizes $B$. Give a CFG that generates $B$.
Let $\Sigma = \{0,1\}$ and let $B$ be the collection of strings that contain at least one $1$ in their second half. In other words, $B = \{uv \mid u \in \Sigma^{\ast}, v...
admin
779
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
pushdown-automata
descriptive
+
–
0
votes
0
answers
107
Michael Sipser Edition 3 Exercise 2 Question 46 (Page No. 158)
Consider the following CFG $G:$ $S \rightarrow SS \mid T$ $T \rightarrow aT b \mid ab$ Describe $L(G)$ and show that $G$ is ambiguous. Give an unambiguous grammar $H$ where $L(H) = L(G)$ and sketch a proof that $H$ is unambiguous.
Consider the following CFG $G:$$S \rightarrow SS \mid T$$T \rightarrow aT b \mid ab$Describe $L(G)$ and show that $G$ is ambiguous. Give an unambiguous grammar $H$ where ...
admin
421
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-grammar
ambiguous
proof
+
–
0
votes
0
answers
108
Michael Sipser Edition 3 Exercise 2 Question 45 (Page No. 158)
Let $A = \{wtw^{R}\mid w,t\in\{0,1\}^{\ast}\:\text{and} \mid w \mid = \mid t \mid \}$. Prove that $A$ is not a CFL.
Let $A = \{wtw^{R}\mid w,t\in\{0,1\}^{\ast}\:\text{and} \mid w \mid = \mid t \mid \}$. Prove that $A$ is not a CFL.
admin
244
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
proof
+
–
0
votes
1
answer
109
Michael Sipser Edition 3 Exercise 2 Question 44 (Page No. 158)
If $A$ and $B$ are languages, define $A \diamond B = \{xy \mid x \in A\: \text{and}\: y \in B \;\text{and} \mid x \mid = \mid y \mid \}$. Show that if $A$ and $B$ are regular languages, then $A \diamond B$ is a CFL.
If $A$ and $B$ are languages, define $A \diamond B = \{xy \mid x \in A\: \text{and}\: y \in B \;\text{and} \mid x \mid = \mid y \mid \}$. Show that if $A$ and $B$ are re...
admin
291
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
regular-language
proof
+
–
0
votes
0
answers
110
Michael Sipser Edition 3 Exercise 2 Question 43 (Page No. 158)
For strings $w4 and $t,4 write $w \circeq t$ if the symbols of $w$ are a permutation of the symbols of $t.$ In other words, $w \circeq t$ if $t$ ... a regular language is context free. What happens in part $(a)$ if $\Sigma$ contains three or more symbols? Prove your answer.
For strings $w4 and $t,4 write $w \circeq t$ if the symbols of $w$ are a permutation of the symbols of $t.$ In other words, $w \circeq t$ if $t$ and $w4 have the same sy...
admin
296
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
proof
+
–
0
votes
0
answers
111
Michael Sipser Edition 3 Exercise 2 Question 42 (Page No. 158)
Let $Y = \{w\mid w = t_{1}\#t_{2}\#\dots t_{k} \:\text{for}\: k\geq 0,\text{each}\: t_{i}\in 1^{\ast}, \text{and}\: t_{i}\neq t_{j} \text{whenever}\: i\neq j\}$.Here $\Sigma = \{1,\#\}$. Prove that $Y$ is not context free.
Let $Y = \{w\mid w = t_{1}\#t_{2}\#\dots t_{k} \:\text{for}\: k\geq 0,\text{each}\: t_{i}\in 1^{\ast}, \text{and}\: t_{i}\neq t_{j} \text{whenever}\: i\neq j\}$.Here $\Si...
admin
167
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
proof
+
–
0
votes
0
answers
112
Michael Sipser Edition 3 Exercise 2 Question 41 (Page No. 158)
Read the definitions of NOPREFIX(A) and NOEXTEND(A) in Question $1.40$. Show that the class of CFLs is not closed under NOPREFIX. Show that the class of CFLs is not closed under NOEXTEND.
Read the definitions of NOPREFIX(A) and NOEXTEND(A) in Question $1.40$.Show that the class of CFLs is not closed under NOPREFIX.Show that the class of CFLs is not closed ...
admin
258
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
+
–
0
votes
0
answers
113
Michael Sipser Edition 3 Exercise 2 Question 40 (Page No. 158)
Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let $C$ be an infinite, prefix-closed, context-free language. Show that $C$ contains an infinite regular subset.
Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let $C$ be an infinite, prefix-closed, context-free languag...
admin
223
views
admin
asked
Oct 10, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
+
–
0
votes
0
answers
114
Michael Sipser Edition 3 Exercise 2 Question 39 (Page No. 158)
For the definition of the shuffle operation. For languages $A$ and $B,$ let the $\text{shuffle}$ of $A$ and $B$ be the language $\{w| w = a_{1}b_{1} \ldots a_{k}b_{k},$ where $ a_{1} · · · a_{k} ∈ A $ and $b_{1} · · · b_{k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ^{*}\}.$ Show that the class of context-free languages is not closed under shuffle.
For the definition of the shuffle operation. For languages $A$ and $B,$ let the $\text{shuffle}$ of $A$ and $B$ be the language $\{w| w = a_{1}b_{1} \ldots a_{k}b_{k},$ ...
admin
257
views
admin
asked
Oct 10, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
shuffle
+
–
0
votes
0
answers
115
Michael Sipser Edition 3 Exercise 2 Question 38 (Page No. 158)
For the definition of the perfect shuffle operation. For languages $A$ and $B,$ let the $\text{perfect shuffle}$ of $A$ and $B$ be the language $\text{{$w| w = a_{1}b_{1} · · · a_{k}b_{k},$ ... k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ$}}.$ Show that the class of context-free languages is not closed under perfect shuffle.
For the definition of the perfect shuffle operation. For languages $A$ and $B,$ let the $\text{perfect shuffle}$ of $A$ and $B$ be the language$\text{{$w| w = a_{1}b_{1} ...
admin
249
views
admin
asked
Oct 10, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
perfect-shuffle
+
–
0
votes
0
answers
116
Michael Sipser Edition 3 Exercise 2 Question 37 (Page No. 158)
Prove the following stronger form of the pumping lemma, where in both pieces $v$ and $y$ must be nonempty when the string $s$ is broken up$.$If $A$ is a context-free language, then there is a number $k$ where, if $s$ is any string in $A$ of ... $i\geq 0,uv^{i}xy^{i}z\in A,$ $v\neq\epsilon$ and $y\neq\epsilon,$and $\mid vxy\mid\leq k.$
Prove the following stronger form of the pumping lemma, where in both pieces $v$ and $y$ must be nonempty when the string $s$ is broken up$.$If $A$ is a context-free lang...
admin
526
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
pumping-lemma
+
–
1
votes
1
answer
117
Michael Sipser Edition 3 Exercise 2 Question 36 (Page No. 158)
Give an example of a language that is not context free but that acts like a $CFL$ in the pumping lemma$.$ Prove that your example works$.$ $\text{(See the analogous example for regular languages in Question 54.)}$
Give an example of a language that is not context free but that acts like a $CFL$ in the pumping lemma$.$ Prove that your example works$.$ $\text{(See the analogous examp...
admin
1.7k
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
pumping-lemma
proof
+
–
0
votes
1
answer
118
Michael Sipser Edition 3 Exercise 2 Question 35 (Page No. 157)
Let $G$ be a $CFG$ in Chomsky normal form that contains $b$ variables$.$ Show that if $G$ generates some string with a derivation having at least $2^{b}$ steps$, L(G)$ is infinite$.$
Let $G$ be a $CFG$ in Chomsky normal form that contains $b$ variables$.$ Show that if $G$ generates some string with a derivation having at least $2^{b}$ steps$, L(G)$ is...
admin
621
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
conjunctive-normal-form
proof
+
–
1
votes
1
answer
119
Michael Sipser Edition 3 Exercise 2 Question 34 (Page No. 157)
Let $G = (V, \Sigma, R, S)$ be the following grammar. $V = \{S, T, U\}; \Sigma = \{0, \#\};$ and $R$ is the set of rules$:$ $S\rightarrow TT\mid U$ $T\rightarrow 0T\mid T0\mid \#$ ... existence of a pumping length $p$ for $B.$ What is the minimum value of $p$ that works in the pumping lemma$?$ Justify your answer$.$
Let $G = (V, \Sigma, R, S)$ be the following grammar. $V = \{S, T, U\}; \Sigma = \{0, \#\};$ and $R$ is the set of rules$:$ $S\rightarrow TT\mid U$ $T\rightarrow 0T\mid T...
admin
1.2k
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
pumping-lemma
proof
+
–
0
votes
1
answer
120
Michael Sipser Edition 3 Exercise 2 Question 33 (Page No. 157)
Show that $F = \{a^{i}b^{j}\mid i = kj$ $\text{for some positive integer $k$\}}$ is not context free$.$
Show that $F = \{a^{i}b^{j}\mid i = kj$ $\text{for some positive integer $k$\}}$ is not context free$.$
admin
256
views
admin
asked
May 4, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
+
–
Page:
« prev
1
2
3
4
5
6
7
8
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register