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

0 votes

0 answers

211

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

0 votes

0 answers

212

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

905 views

admin asked Apr 21, 2019

1 votes

0 answers

213

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

0 votes

1 answer

214

Michael Sipser Edition 3 Exercise 1 Question 12 (Page No. 85)
Let $D = \{w \mid w $ contains an even number of a’s and an odd number of b’s and does not contain the substring $ab\}.$ Give a $\text{DFA}$ with five states that recognizes $\text{D}$ and a regular expression that generates $\text{D.}$ $($Suggestion: Describe $D$ more simply$.)$

Let $D = \{w \mid w $ contains an even number of a’s and an odd number of b’s and does not contain the substring $ab\}.$ Give a $\text{DFA}$ with five states that rec...

admin

1.5k views

admin asked Apr 21, 2019

0 votes

1 answer

215

Michael Sipser Edition 3 Exercise 1 Question 11 (Page No. 85)
Prove that every $\text{NFA}$ can be converted to an equivalent one that has a single accept state.

Prove that every $\text{NFA}$ can be converted to an equivalent one that has a single accept state.

admin

1.1k views

admin asked Apr 21, 2019

0 votes

1 answer

216

Michael Sipser Edition 3 Exercise 1 Question 10 (Page No. 85)
Use the construction in the proof of $\text{Theorem 1.49}$ to give the state diagrams of $NFA's$ recognizing the star of the languages described in $\text{\{w| w contains at least three 1s\}}$ $\text{\{w| w contains at least two 0's and at most one 1\}}$ $\text{The empty set}$

Use the construction in the proof of $\text{Theorem 1.49}$ to give the state diagrams of $NFA's$ recognizing the star of the languages described in$\text{\{w| w contains ...

admin

2.0k views

admin asked Apr 21, 2019

0 votes

0 answers

217

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.1k views

admin asked Apr 21, 2019

0 votes

1 answer

218

Michael Sipser Edition 3 Exercise 1 Question 8 (Page No. 84)
Use the construction in the proof of $\text{Theorem 1.45}$ to give the state diagrams of $\text{NFA's}$ ...

Use the construction in the proof of $\text{Theorem 1.45}$ to give the state diagrams of $\text{NFA’s}$ recognizing the union of the languages described in$L_{1}=\text{...

admin

4.6k views

admin asked Apr 21, 2019

1 votes

1 answer

219

Michael Sipser Edition 3 Exercise 1 Question 7 (Page No. 84)
Give state diagrams of $\text{NFA's}$ with the specified number of states recognizing each of the following languages. In all parts, the alphabet is $\{0,1\}.$ $\text{The language \{w| w ends with 00\} with three states}$ ... $\text{The language}$ $\{\epsilon\}$ $\text{with one state}$ $\text{The language 0* with one state}$

Give state diagrams of $\text{NFA's}$ with the specified number of states recognizing each of the following languages. In all parts, the alphabet is $\{0,1\}.$$\text{The ...

admin

15.1k views

admin asked Apr 21, 2019

4 votes

1 answer

220

Michael Sipser Edition 3 Exercise 1 Question 6 (Page No. 84)
Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is $\{0,1\}.$ $\text{\{w| w begins with a 1 and ends with a 0\}}$ $\text{\{w| w contains at least three 1s\}}$ ... $\text{The empty set}$ $\text{All strings except the empty string}$

Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is $\{0,1\}.$$\text{\{w| w begins with a 1 and ends with a 0\}}$$\text{\{w| w ...

admin

19.4k views

admin asked Apr 21, 2019

9 votes

1 answer

221

Michael Sipser Edition 3 Exercise 1 Question 5 (Page No. 84)
Each of the following languages is the complement of a simpler language. In each part, construct a $\text{DFA}$ for the simpler language, then use it to give the state diagram of a $\text{DFA}$ ... $\text{\{w| w is any string except a and b\}}$

Each of the following languages is the complement of a simpler language. In each part, construct a $\text{DFA}$ for the simpler language, then use it to give the state di...

admin

16.0k views

admin asked Apr 21, 2019

4 votes

0 answers

222

Michael Sipser Edition 3 Exercise 1 Question 4 (Page No. 83)
Each of the following languages is the intersection of two simpler languages. In each part, construct $\text{DFAs}$ for the simpler languages, then combine them using the construction discussed in footnote $\text{3 (page 46)}$ to give the state diagram of ... $\text{\{w| w has even length and an odd number of a's\}}$

Each of the following languages is the intersection of two simpler languages. In each part, construct $\text{DFAs}$ for the simpler languages, then combine them using the...

admin

1.8k views

admin asked Apr 21, 2019

0 votes

0 answers

223

Michael Sipser Edition 3 Exercise 1 Question 3 (Page No. 83)
The formal description of a $\text{DFA}$ $\text{M}$ is $({q1, q2, q3, q4, q5}, {u, d}, δ, q3, {q3}),$ where $\text{δ}$ is given by the following table. Give the state diagram of this machine.

The formal description of a $\text{DFA}$ $\text{M}$ is $({q1, q2, q3, q4, q5}, {u, d}, δ, q3, {q3}),$ where $\text{δ}$ is given by the following table. Give the state ...

admin

793 views

admin asked Apr 21, 2019

0 votes

0 answers

224

Michael Sipser Edition 3 Exercise 1 Question 2 (Page No. 83)
Give the formal description of the machines $\text{M1}$ and $\text{M2.}$

Give the formal description of the machines $\text{M1}$ and $\text{M2.}$

admin

834 views

admin asked Apr 21, 2019

0 votes

0 answers

225

Michael Sipser Edition 3 Exercise 1 Question 1 (Page No. 83)
The following are the state diagrams of two $\text{DFAs,}$ $\text{M1}$, and $\text{M2.}$ Answer the following questions about each of these machines. What is the start state? What is the set of accept states? What sequence ... $\text{aabb?}$ Does the machine accept the string $\text{aabb?}$ Does the machine accept the string $\epsilon?$

The following are the state diagrams of two $\text{DFAs,}$ $\text{M1}$, and $\text{M2.}$ Answer the following questions about each of these machines.What is the start sta...

admin

1.5k views

admin asked Apr 21, 2019

0 votes

0 answers

226

Michael Sipser Edition 3 Exercise 0 Question 15 (Page No. 28)
Use Theorem $0.25$ to derive a formula for calculating the size of the monthly payment for a mortgage in terms of the principal $P,$ the interest rate $I,$ and the number of payments, $t.$ Assume that after $t$ payments have been made, ... $5\%$ annual interest rate. Hint$:$ Theorem $0.25$ are explained in page number $24 - 25.$

Use Theorem $0.25$ to derive a formula for calculating the size of the monthly payment for a mortgage in terms of the principal $P,$ the interest rate $I,$ and the number...

admin

264 views

admin asked Apr 14, 2019

0 votes

0 answers

227

Michael Sipser Edition 3 Exercise 0 Question 14 (Page No. 28)
Ramsey's theorem$:$ Let $G$ be a graph. A clique in $G$ is a sub-graph in which every two nodes are connected by an edge. An anti-clique also called an independent set, is a sub-graph in which every two nodes are not connected ... graph with $n$ nodes contains either a clique or an anti-clique with at least $\frac{1}{2}log_{2}n$ nodes.

Ramsey’s theorem$:$ Let $G$ be a graph. A clique in $G$ is a sub-graph in which every two nodes are connected by an edge. An anti-clique also called an independent set,...

admin

474 views

admin asked Apr 14, 2019

0 votes

1 answer

228

Michael Sipser Edition 3 Exercise 0 Question 13 (Page No. 27)
Show that every graph with two or more nodes contains two nodes that have equal degrees.

Show that every graph with two or more nodes contains two nodes that have equal degrees.

admin

560 views

admin asked Apr 14, 2019

1 votes

1 answer

229

Michael Sipser Edition 3 Exercise 0 Question 12 (Page No. 27)
Find the error in the following proof that all horses are the same color. CLAIM: In any set of h horses, all horses are the same color. PROOF: By induction on $h.$ Basis: For $h = 1.$ In any set containing just one horse, ... $H$ must be the same color, and the proof is complete.

Find the error in the following proof that all horses are the same color.CLAIM: In any set of h horses, all horses are the same color.PROOF: By induction on $h.$Basis: Fo...

admin

1.5k views

admin asked Apr 14, 2019

0 votes

1 answer

230

Michael Sipser Edition 3 Exercise 0 Question 11 (Page No. 27)
Let $S(n) = 1 + 2 + · · · + n$ be the sum of the first $n$ natural numbers and let $C(n) = 1^{3} + 2^{3} + · · · + n^{3}$ be the sum of the first $n$ cubes. Prove the following equalities by induction on $n,$ ... $C(n)=\frac{1}{4}(n^{4}+2n^{3}+n^{2}=\frac{1}{4}n^{2}(n+1)^{2}.$

Let $S(n) = 1 + 2 + · · · + n$ be the sum of the first $n$ natural numbers and let $C(n) = 1^{3} + 2^{3} + · · · + n^{3}$ be the sum of the first $n$ cubes. Prove t...

admin

2.2k views

admin asked Apr 14, 2019

0 votes

0 answers

231

Michael Sipser Edition 3 Exercise 0 Question 10 (Page No. 27)
Find the error in the following proof that $2 = 1.$Consider the equation $a = b.$ Multiply both sides by a to obtain $a^{2} = ab.$ Subtract $b^{2}$ from both sides to get $a^{2}-b^{2}=ab-b^{2}.$ ... each side by $(a−b)$ to get $a+b = b.$ Finally, let $a$ and $b$ equal $1,$ which shows that $2 = 1.$

Find the error in the following proof that $2 = 1.$Consider the equation $a = b.$ Multiply both sides by a to obtain $a^{2} = ab.$ Subtract $b^{2}$ from both sides to get...

admin

199 views

admin asked Apr 14, 2019

0 votes

0 answers

232

Michael Sipser Edition 3 Exercise 0 Question 9 (Page No. 27)
Write a formal description of the following graph.

Write a formal description of the following graph.

admin

473 views

admin asked Apr 13, 2019

0 votes

0 answers

233

Michael Sipser Edition 3 Exercise 0 Question 8 (Page No. 26)
Consider the undirected graph G= (V, E) where V , the set of nodes, is {1, 2, 3, 4} and E, the set of edges, is {{1, 2}, {2, 3}, {1, 3}, {2, 4}, {1, 4}}. Draw the graph G. What are the degrees of each node? Indicate a path from node 3 to node 4 on your drawing of G.

Consider the undirected graph G= (V, E) where V , the set of nodes, is {1, 2, 3, 4} and E, the set of edges, is {{1, 2}, {2, 3}, {1, 3}, {2, 4}, {1, 4}}. Draw the graph G...

admin

359 views

admin asked Apr 13, 2019

0 votes

0 answers

234

Michael Sipser Edition 3 Exercise 0 Question 7 (Page No. 26)
For each part, give a relation that satisfies the condition. Reflexive and symmetric but not transitive Reflexive and transitive but not symmetric Symmetric and transitive but not reflexive

For each part, give a relation that satisfies the condition.Reflexive and symmetric but not transitiveReflexive and transitive but not symmetricSymmetric and transitive b...

admin

273 views

admin asked Apr 13, 2019

0 votes

1 answer

235

Michael Sipser Edition 3 Exercise 0 Question 6 (Page No. 26)
Let X be the set {1, 2, 3, 4, 5} and Y be the set {6, 7, 8, 9, 10}. The unary function$ f: X→Y$ and the binary function $g: X Y →Y$ are described in the following tables. a. What is the value of f(2)? b. What are the range and ... . What is the value of g(2, 10)? d. What are the range and domain of g? e. What is the value of g(4, f(4))?

Let X be the set {1, 2, 3, 4, 5} and Y be the set {6, 7, 8, 9, 10}. The unary function$ f: X→Y$ and the binary function $g: X × Y →Y$ are described in the following ...

admin

629 views

admin asked Apr 13, 2019

0 votes

2 answers

236

Michael Sipser Edition 3 Exercise 0 Question 5 (Page No. 26)
If C is a set with c elements, how many elements are in the power set of C? Explain your answer.

If C is a set with c elements, how many elements are in the power set of C? Explain your answer.

admin

2.7k views

admin asked Apr 13, 2019

0 votes

1 answer

237

Michael Sipser Edition 3 Exercise 0 Question 4 (Page No. 26)
If A has a elements and B has b elements, how many elements are in A × B? Explain your answer.

If A has a elements and B has b elements, how many elements are in A × B? Explain your answer.

admin

386 views

admin asked Apr 13, 2019

0 votes

1 answer

238

Michael Sipser Edition 3 Exercise 0 Question 3 (Page No. 26)
Let A be the set {x, y, z} and B be the set {x, y}. a. Is A a subset of B? b. Is B a subset of A? c. What is A ∪ B? d. What is A ∩ B? e. What is A × B? f. What is the power set of B?

Let A be the set {x, y, z} and B be the set {x, y}.a. Is A a subset of B?b. Is B a subset of A?c. What is A ∪ B?d. What is A ∩ B?e. What is A × B?f. What is the powe...

admin

479 views

admin asked Apr 13, 2019

0 votes

0 answers

239

Michael Sipser Edition 3 Exercise 0 Question 2 (Page No. 25)
Write formal descriptions of the following sets. a. The set containing the numbers 1, 10, and 100 b. The set containing all integers that are greater than 5 c. The set containing all natural numbers that are less than 5 d. The set containing the string aba e. The set containing the empty string f. The set containing nothing at all

Write formal descriptions of the following sets.a. The set containing the numbers 1, 10, and 100b. The set containing all integers that are greater than 5c. The set conta...

admin

345 views

admin asked Apr 13, 2019

1 votes

0 answers

240

Michael Sipser Edition 3 Exercise 0 Question 1 (Page No. 25)
Examine the following formal descriptions of sets so that you understand which members they contain. Write a short informal English description of each set. a. {1, 3, 5, 7, . . . } b. { . . . , −4, −2, 0, 2, 4, . . . } c. {n| n = 2m for ... {w| w is a string of 0s and 1s and w equals the reverse of w} f. {n| n is an integer and n = n + 1}

Examine the following formal descriptions of sets so that you understand which members they contain. Write a short informal English description of each set.a. {1, 3, 5, 7...

admin

508 views

admin asked Apr 13, 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