Recent questions tagged michael-sipser / GATE Overflow for GATE CSE

0 votes

1 answer

151

Michael Sipser Edition 3 Exercise 2 Question 2 (Page No. 154)
Use the languages $A=\{a^{m}b^{n}c^{n}|m,n\geq 0\}$ and $B=\{a^{n}b^{n}c^{m}|m,n\geq 0\}$ together with $\text{Example 2.36}$ to show that the class of context-free languages is not closed under ... $(a)$ and $\text{DeMorgan's law (Theorem 0.20)}$ to show that the class of context-free languages is not closed under complementation.

Use the languages $A=\{a^{m}b^{n}c^{n}|m,n\geq 0\}$ and $B=\{a^{n}b^{n}c^{m}|m,n\geq 0\}$ together with $\text{Example 2.36}$ to show that the class of context-free langu...

admin

475 views

admin asked Apr 30, 2019

0 votes

0 answers

152

Michael Sipser Edition 3 Exercise 2 Question 1 (Page No. 154)
Recall the $\text{CFG}$ $G_{4}$ that we gave in $\text{Example 2.4}.$ For convenience,let’s rename it’s variable with single letters as follows, $E\rightarrow E+T|T$ $T\rightarrow T\times F|F$ $F\rightarrow (E)|a$ Give parse trees and derivations for each string. $a$ $a+a$ $a+a+a$ $((a))$

Recall the $\text{CFG}$ $G_{4}$ that we gave in $\text{Example 2.4}.$ For convenience,let’s rename it’s variable with single letters as follows, ...

admin

404 views

admin asked Apr 30, 2019

0 votes

0 answers

153

Michael Sipser Edition 3 Exercise 1 Question 73 (Page No. 93)
Let $\sum = \{0,1, \#\}.$ Let $C = \{x\#x^{R}\#x| x\in\{0,1\}^{*}\}.$Show that $\overline{C}$ is a $\text{CFL}.$

Let $\sum = \{0,1, \#\}.$ Let $C = \{x\#x^{R}\#x| x\in\{0,1\}^{*}\}.$Show that $\overline{C}$ is a $\text{CFL}.$

admin

189 views

admin asked Apr 30, 2019

0 votes

0 answers

154

Michael Sipser Edition 3 Exercise 1 Question 72 (Page No. 93)
Let $M_{1}$ and $M_{2}$ be $\text{DFA's}$ that have $k_{1}$ and $k_{2}$ states, respectively, and then let $U = L(M_{1})\cup L(M_{2}).$ Show that if $U\neq\phi$ then $U$ contains some string $s,$ where $|s| < max(k1, k2).$ Show that if $U\neq\sum^{*},$ then $U$ excludes some string $s,$ where $|s| < k1k2.$

Let $M_{1}$ and $M_{2}$ be $\text{DFA's}$ that have $k_{1}$ and $k_{2}$ states, respectively, and then let $U = L(M_{1})\cup L(M_{2}).$Show that if $U\neq\phi$ then $U$ c...

admin

325 views

admin asked Apr 30, 2019

2 votes

2 answers

155

Michael Sipser Edition 3 Exercise 1 Question 71 (Page No. 93)
Let $\sum = \{0,1\}$ Let $A=\{0^{k}u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$ Show that $A$ is regular. Let $B=\{0^{k}1u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$Show that $B$ is not regular.

Let $\sum = \{0,1\}$Let $A=\{0^{k}u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$ Show that $A$ is regular.Let $B=\{0^{k}1u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}....

admin

508 views

admin asked Apr 30, 2019

0 votes

1 answer

156

Michael Sipser Edition 3 Exercise 1 Question 70 (Page No. 93)
We define the $\text{avoids}$ operation for languages $A$ and $B$ to be $\text{A avoids B = {w| w ∈ A and w doesn’t contain any string in B as a substring}.}$ Prove that the class of regular languages is closed under the ${avoids}$ operation.

We define the $\text{avoids}$ operation for languages $A$ and $B$ to be $\text{A avoids B = {w| w ∈ A and w doesn’t contain any string in B as a substring}.}$ Prove t...

admin

489 views

admin asked Apr 30, 2019

1 votes

0 answers

157

Michael Sipser Edition 3 Exercise 1 Question 69 (Page No. 93)
Let $\sum=\{0,1\}.$ Let $WW_{k}=\{ww|w\in \sum^{*}$ and $w$ is of length $k\}.$ Show that for each $k,$ no DFA can recognize $WW_{k}$ with fewer than $2^{k}$ states. Describe a much smaller $NFA$ for $\overline{WW_{k}},$ the complement of $WW_{k}.$

Let $\sum=\{0,1\}.$ Let $WW_{k}=\{ww|w\in \sum^{*}$ and $w$ is of length $k\}.$Show that for each $k,$ no DFA can recognize $WW_{k}$ with fewer than $2^{k}$ states.Descri...

admin

335 views

admin asked Apr 30, 2019

0 votes

0 answers

158

Michael Sipser Edition 3 Exercise 1 Question 68 (Page No. 93)
In the traditional method for cutting a deck of playing cards, the deck is arbitrarily split two parts, which are exchanged beforereassembling the deck. In a more complex cut, called $\text{Scarne's cut,}$ the deck is broken into three parts ... $ CUT(CUT(B)).}$ Show that the class of regular languages is closed under $\text{CUT}.$

In the traditional method for cutting a deck of playing cards, the deck is arbitrarily split two parts, which are exchanged beforereassembling the deck. In a more complex...

admin

525 views

admin asked Apr 30, 2019

0 votes

0 answers

159

Michael Sipser Edition 3 Exercise 1 Question 67 (Page No. 93)
Let the rotational closure of language $A$ be $RC(A) = \{yx| xy ∈ A\}.$ Show that for any language $A,$ we have $RC(A) = RC(RC(A)).$ Show that the class of regular languages is closed under rotational closure.

Let the rotational closure of language $A$ be $RC(A) = \{yx| xy ∈ A\}.$Show that for any language $A,$ we have $RC(A) = RC(RC(A)).$Show that the class of regular langua...

admin

424 views

admin asked Apr 30, 2019

0 votes

0 answers

160

Michael Sipser Edition 3 Exercise 1 Question 66 (Page No. 93)
A $\text{homomorphism}$ is a function $f : Σ→Γ^{*}$ from one alphabet to strings overanother alphabet. We can extend $f$ to operate on strings by defining $f(w) = f(w_{1})f(w_{2})...f(w_{n}),$ ... Is it a DFA in every case$?$ Show, by giving an example, that the class of non-regular languages is not closed under homomorphism.

A $\text{homomorphism}$ is a function $f : Σ→Γ^{*}$ from one alphabet to strings overanother alphabet. We can extend $f$ to operate on strings by defining $f(w) = f(w...

admin

581 views

admin asked Apr 30, 2019

0 votes

0 answers

161

Michael Sipser Edition 3 Exercise 1 Question 65 (Page No. 93)
Prove that for each $n > 0,$ a language $B_{n}$ exists where $B_{n}$ is recognizable by an $\text{NFA}$ that has $n$ states, and if $B_{n} = A_{1}\cup...\cup A_{k},$ for regular languages $A_{i},$ then at least one of the $A_{i}$ requires a $\text{DFA}$ with exponentially many states$.$

Prove that for each $n 0,$ a language $B_{n}$ exists where$B_{n}$ is recognizable by an $\text{NFA}$ that has $n$ states, andif $B_{n} = A_{1}\cup...\cup A_{k},$ for reg...

admin

304 views

admin asked Apr 30, 2019

0 votes

0 answers

162

Michael Sipser Edition 3 Exercise 1 Question 64 (Page No. 92)
Let $N$ be an $\text{NFA}$ with $k$ states that recognizes some language $A.$ Show that if $A$ is nonempty, A contains some string of length at most k. Show, by giving an example, that $\text{part (a)}$ is not necessarily ... ;s shortest member strings are of length exponential in $k.$ Come as close to the bound in $(c)$ as you can$.$

Let $N$ be an $\text{NFA}$ with $k$ states that recognizes some language $A.$Show that if $A$ is nonempty, A contains some string of length at most k.Show, by giving an e...

admin

587 views

admin asked Apr 30, 2019

0 votes

0 answers

163

Michael Sipser Edition 3 Exercise 1 Question 63 (Page No. 92)
Let $A$ be an infinite regular language. Prove that $A$ can be split into two infinite disjoint regular subsets. Let $B$ and $D$ be two languages. Write $B\subseteqq D$ if $B\subseteq D$ and $D$ contains infinitely many ... regular languages where $B\subseteqq D,$ then we can find a regular language $C$ where $B\subseteqq C\subseteqq D.$

Let $A$ be an infinite regular language. Prove that $A$ can be split into two infinite disjoint regular subsets.Let $B$ and $D$ be two languages. Write $B\subseteqq D$ if...

admin

346 views

admin asked Apr 30, 2019

0 votes

0 answers

164

Michael Sipser Edition 3 Exercise 1 Question 62 (Page No. 92)
Let $\sum =\{a, b\}.$ For each $k\geq 1,$ let $D_{k}$ be the language consisting of all strings that have at least one a among the last $k$ symbols$.$Thus $D_{k}=\sum^{*}a(\sum \cup \epsilon)^{k-1}$.Describe a $\text{DFA}$ with at most $k+ 1$ states that recognizes $D_{k}$ in terms of both a state diagram and a formal description.

Let $\sum =\{a, b\}.$ For each $k\geq 1,$ let $D_{k}$ be the language consisting of all strings that have at least one a among the last $k$ symbols$.$Thus $D_{k}=\sum^{*}...

admin

221 views

admin asked Apr 30, 2019

0 votes

0 answers

165

Michael Sipser Edition 3 Exercise 1 Question 61 (Page No. 92)
Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the right-hand end$.$ Thus $C_{k}=\sum^{*}a\sum^{k-1}.$ Prove that for each $k,$ $\text{no DFA}$ can recognize $C_{k}$ with fewer than $2^{k}$ states.

Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the right-hand end$.$ Thus $C_{k}...

admin

294 views

admin asked Apr 30, 2019

0 votes

1 answer

166

Michael Sipser Edition 3 Exercise 1 Question 60 (Page No. 92)
Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the right-hand end$.$ Thus $C_{k}=\sum^{*}a\sum^{k-1}.$ Describe an $\text{NFA}$ with $k + 1$ states that recognizes $C_{k}$ in terms of both a state diagram and a formal description$.$

Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the right-hand end$.$ Thus $C_{k}...

admin

2.6k views

admin asked Apr 30, 2019

0 votes

0 answers

167

Michael Sipser Edition 3 Exercise 1 Question 59 (Page No. 92)
Let $M = (Q, Σ, δ, q_{0}, F)$ be a $\text{DFA}$ and let $h$ be a state of $M$ called its $\text{ home }.$ A $\text{synchronizing sequence}$ for $M$ and $h$ is a string $s\in\sum^{*}$ ... $\text{DFA,}$ then it has a synchronizing sequence of length at most $k^{3}.$Can you improve upon this bound$?$

Let $M = (Q, Σ, δ, q_{0}, F)$ be a $\text{DFA}$ and let $h$ be a state of $M$ called its $\text{“home”}.$ A $\text{synchronizing sequence}$ for $M$ and $h$ is a str...

admin

617 views

admin asked Apr 30, 2019

0 votes

0 answers

168

Michael Sipser Edition 3 Exercise 1 Question 58 (Page No. 92)
If $A$ is any language,let $A_{\frac{1}{2}-\frac{1}{3}}$ be the set of all strings in $A$ with their ,middle thirds removed so that $A_{\frac{1}{2}-\frac{1}{3}}=\{\text{xz|for some y,|x|=|y|=|z| and xyz $\in$ A\}}.$ Show that if $A$ is regular,then $A_{\frac{1}{2}-\frac{1}{3}}$ is not necessarily regular.

If $A$ is any language,let $A_{\frac{1}{2}-\frac{1}{3}}$ be the set of all strings in $A$ with their ,middle thirds removed so that$A_{\frac{1}{2}-\frac{1}{3}}=\{\text{xz...

admin

223 views

admin asked Apr 30, 2019

0 votes

0 answers

169

Michael Sipser Edition 3 Exercise 1 Question 57 (Page No. 92)
If $A$ is any language,let $A_{\frac{1}{2}-}$ be the set of all first halves of strings in $A$ so that $A_{\frac{1}{2}-}=\{\text{x|for some y,|x|=|y| and xy $\in$ A\}}.$ Show that if $A$ is regular,then so is $A_{\frac{1}{2}-}.$

If $A$ is any language,let $A_{\frac{1}{2}-}$ be the set of all first halves of strings in $A$ so that $A_{\frac{1}{2}-}=\{\text{x|for some y,|x|=|y| and xy $\in$ A\}}.$...

admin

259 views

admin asked Apr 30, 2019

0 votes

0 answers

170

Michael Sipser Edition 3 Exercise 1 Question 56 (Page No. 91)
If $A$ is a set of natural numbers and $k$ is a natural number greater than $1,$ let $B_{k}(A)=\{\text{w| w is the representation in base k of some number in A\}}.$ Here, we do not allow leading $0's$ in the representation ... a set $A$ for which $B_{2}(A)$ is regular but $B_{3}(A)$ is not regular$.$ Prove that your example works.

If $A$ is a set of natural numbers and $k$ is a natural number greater than $1,$ let $B_{k}(A)=\{\text{w| w is the representation in base k of some number in A\}}.$ Here,...

admin

331 views

admin asked Apr 30, 2019

1 votes

1 answer

171

Michael Sipser Edition 3 Exercise 1 Question 55 (Page No. 91)
The pumping lemma says that every regular language has a pumping length $p,$ such that every string in the language can be pumped if it has length $p$ or more. If $p$ is a pumping length for language $A,$ so is any length $p^{'}\geq p.$ The minimum pumping ... $\epsilon$ $1^{*}01^{*}01^{*}$ $10(11^{*}0)^{*}0$ $1011$ $\sum^{*}$

The pumping lemma says that every regular language has a pumping length $p,$ such that every string in the language can be pumped if it has length $p$ or more. If $p$ is ...

admin

2.3k views

admin asked Apr 30, 2019

0 votes

1 answer

172

Michael Sipser Edition 3 Exercise 1 Question 54 (Page No. 91)
Consider the language $F=\{a^{i}b^{j}c^{k}|i,j,k\geq 0$ $\text{and if}$ $ i = 1$ $\text{then} $ $ j=k\}.$ Show that $F$ is not regular. Show that $F$ acts like a regular language in the pumping lemma. ... three conditions of the pumping lemma for this value of $p.$ Explain why parts $(a)$ and $(b)$ do not contradict the pumping lemma.

Consider the language $F=\{a^{i}b^{j}c^{k}|i,j,k\geq 0$ $\text{and if}$ $ i = 1$ $\text{then} $ $ j=k\}.$Show that $F$ is not regular.Show that $F$ acts like a regular la...

admin

937 views

admin asked Apr 30, 2019

0 votes

0 answers

173

Michael Sipser Edition 3 Exercise 1 Question 53 (Page No. 91)
Let $\sum=\{0,1,+,=\}$ and $ADD=\{x=y+z|x,y,z$ $\text{are binary integers,and}$ $x$ $\text{is the sum of}$ $y$ $\text{and}$ $z\}.$ Show that $\text{ADD}$ is not a regular.

Let $\sum=\{0,1,+,=\}$ and $ADD=\{x=y+z|x,y,z$ $\text{are binary integers,and}$ $x$ $\text{is the sum of}$ $y$ $\text{and}$ $z\}.$ Show that $\text{ADD}$ is not a regular...

admin

287 views

admin asked Apr 30, 2019

1 votes

0 answers

174

Michael Sipser Edition 3 Exercise 1 Question 52 (Page No. 91)
$\text{Myhill-Nerode theorem.}$ Refer to $\text{Question 51}.$Let $L$ be a language and let $X$ be a set of strings. Say that $X$ is $\text{pairwise distinguishable}$ by $L$ if every two distinct strings in $X$ are ... $\text{DFA}$ recognizing it$.$

$\text{Myhill–Nerode theorem.}$ Refer to $\text{Question 51}.$Let $L$ be a language and let $X$ be a set of strings. Say that $X$ is $\text{pairwise distinguishable}$ b...

admin

392 views

admin asked Apr 30, 2019

0 votes

0 answers

175

Michael Sipser Edition 3 Exercise 1 Question 51 (Page No. 90)
Let $x$ and $y$ be strings and let $L$ be any language. We say that $x$ and $y$ are $\text{distinguishable}$ by $L$ if some string $z$ exists whereby exactly one of the strings $xz$ and $yz$ ... $≡L$ is an equivalence relation. A $\text{palindrome}$ is a string that reads the same forward and backward.

Let $x$ and $y$ be strings and let $L$ be any language. We say that $x$ and $y$ are $\text{distinguishable}$ by $L$ if some string $z$ exists whereby exactly one of the s...

admin

308 views

admin asked Apr 30, 2019

1 votes

0 answers

176

Michael Sipser Edition 3 Exercise 1 Question 50 (Page No. 90)
Read the informal definition of the finite state transducer given in Question $24.$ Prove that $\text{no FST}$ can output $w^{R}$ for every input $w$ if the input and output alphabets are $\{0,1\}.$

Read the informal definition of the finite state transducer given in Question $24.$ Prove that $\text{no FST}$ can output $w^{R}$ for every input $w$ if the input and out...

admin

194 views

admin asked Apr 30, 2019

0 votes

1 answer

177

Michael Sipser Edition 3 Exercise 1 Question 49 (Page No. 90)
Let $B=\{1^{k}y|y\in\{0,1\}^{*}$ $\text{ and y contains at least}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $B$ is a regular language. Let $C=\{1^{k}y|y\in\{0,1\}^{*}$ $\text{ and y contains at most}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $C$ isn’t a regular language.

Let $B=\{1^{k}y|y\in\{0,1\}^{*}$ $\text{ and y contains at least}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $B$ is a regular language.Let $C=\{1^{k}y|y\in\{0...

admin

444 views

admin asked Apr 30, 2019

1 votes

0 answers

178

Michael Sipser Edition 3 Exercise 1 Question 48 (Page No. 90)
Let $\sum = \{0,1\}$ and let $D = \{w|w$ $\text{contains an equal number of occurrences of the sub strings 01 and 10}\}.$ Thus $101\in D$ because $101$ contains a single $01$ and a single $10,$ but $1010\notin D$ because $1010$ contains two $10's$ and one $01.$ Show that $D$ is a regular language.

Let $\sum = \{0,1\}$ and let $D = \{w|w$ $\text{contains an equal number of occurrences of the sub strings 01 and 10}\}.$Thus $101\in D$ because $101$ contains a single ...

admin

254 views

admin asked Apr 30, 2019

0 votes

0 answers

179

Michael Sipser Edition 3 Exercise 1 Question 47 (Page No. 90)
Let $\sum=\{1,\#\}$ and let $Y=\{w|w=x_{1}\#x_{2}\#...\#x_{k}$ $\text{for}$ $k\geq 0,$ $\text{each}$ $ x_{i}\in 1^{*},$ $\text{and}$ $x_{i}\neq x_{j}$ $\text{for}$ $i\neq j\}.$ Prove that $Y$ is not regular.

Let $\sum=\{1,\#\}$ and let $Y=\{w|w=x_{1}\#x_{2}\#...\#x_{k}$ $\text{for}$ $k\geq 0,$ $\text{each}$ $ x_{i}\in 1^{*},$ $\text{and}$ $x_{i}\neq x_{j}$ $\text{for}$ $i\...

admin

321 views

admin asked Apr 30, 2019

0 votes

0 answers

180

Michael Sipser Edition 3 Exercise 1 Question 46 (Page No. 90)
Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection,and complement. $\{0^{n}1^{m}0^{n}|m,n\geq 0\}$ $\{0^{m}1^{n}|m\neq n\}$ $\{w|w\in\{0,1\}^{*} \text{is not a palindrome}\}$ $\{wtw|w,t\in\{0,1\}^{+}\}$

Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection,and compleme...

admin

497 views

admin asked Apr 30, 2019

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true