DISCRETE MATH
8th Edition
ISBN: 9781266712326
Author: ROSEN
Publisher: MCG CUSTOM
expand_more
expand_more
format_list_bulleted
Videos
Textbook Question
Chapter 13.5, Problem 8E
Construct a Turing machine with tape symbols 0, 1, and B that, given a bit string as input, replaces all 0s on the tape with 1s and does not change any of the 1s on the tape.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
-xx0.
B2 If Xfx(x) find the MGF in the case that
fx(x) =
-
1
28
exp{-|x − a\/ẞ},
Use the MGF to compute E(X) and Var(X).
Name
Assume there is the following simplified grade book:
Homework Labs | Final Exam | Project
Avery
95
98
90
100
Blake
90
96
Carlos
83
79
Dax
55
30
228
92
95
79
90
65
60
Assume that the weights used to compute the final grades are homework 0.3, labs 0.2,
the final 0.35, and the project 0.15.
| Write an explicit formula to compute Avery's final grade using a single
inner product.
Write an explicit formula to compute everyone's final grade simultane-
ously using a single matrix-vector product.
1. Explicitly compute by hand (with work shown) the following Frobenius inner
products
00
4.56 3.12
(a) ((º º º). (156
(b)
10.9
-1
0
2)),
Fro
5')) Fro
Chapter 13 Solutions
DISCRETE MATH
Ch. 13.1 - Exercises 1-3 refer to the grammar with start...Ch. 13.1 - Exercises 1-3 refer to the grammar with start...Ch. 13.1 - Prob. 3ECh. 13.1 - Let G=(V,T,S,P) be the phrase-structure grammar...Ch. 13.1 - Prob. 5ECh. 13.1 - Prob. 6ECh. 13.1 - Prob. 7ECh. 13.1 - Show that the grammar given in Example 5 generates...Ch. 13.1 - Prob. 9ECh. 13.1 - Prob. 10E
Ch. 13.1 - Construct a derivation of 021222 in the grammar...Ch. 13.1 - Show that the grammar given in Example 7 generates...Ch. 13.1 - s13. Find a phrase-structure grammar for each of...Ch. 13.1 - Find a phrase-structure grammar for each of these...Ch. 13.1 - Find a phrase-structure grammar for each of these...Ch. 13.1 - Construct phrase-structure grammars to generate...Ch. 13.1 - Construct phrase-structure grammars to generate...Ch. 13.1 - Construct phrase-structure grammars to generate...Ch. 13.1 - Prob. 19ECh. 13.1 - A palindrome is a string that reads the same...Ch. 13.1 - Let G1 and G2 be context-free grammars, generating...Ch. 13.1 - Prob. 22ECh. 13.1 - Construct derivation trees for the sentences in...Ch. 13.1 - Let G be the grammar with V={a,b,c,S};T={a,b,c} ;...Ch. 13.1 - Prob. 25ECh. 13.1 - Prob. 26ECh. 13.1 - Prob. 27ECh. 13.1 - a) Explain what the productions are in a grammar...Ch. 13.1 - Prob. 29ECh. 13.1 - a) Construct a phrasestructure grammar for the set...Ch. 13.1 - Give production rules in Backus-Naur form for an...Ch. 13.1 - Prob. 32ECh. 13.1 - Prob. 33ECh. 13.1 - Prob. 34ECh. 13.1 - Prob. 35ECh. 13.1 - Prob. 36ECh. 13.1 - Prob. 37ECh. 13.1 - Prob. 38ECh. 13.1 - Prob. 39ECh. 13.1 - Prob. 40ECh. 13.1 - Prob. 41ECh. 13.1 - Let G be a grammar and let R be the relation...Ch. 13.2 - Draw the state diagrams for the finite-state...Ch. 13.2 - Give the state tables for the finite-state machine...Ch. 13.2 - Find the output generated from the input string...Ch. 13.2 - Find the output generated from the input string...Ch. 13.2 - Find the output for each of these input strings...Ch. 13.2 - Find the output for each of these input strings...Ch. 13.2 - Construct a finite-state machine that models an...Ch. 13.2 - Prob. 8ECh. 13.2 - Construct a finite-state machine that delays an...Ch. 13.2 - Construct a finite-state machine that changes...Ch. 13.2 - Construct a finite-state machine for the log-on...Ch. 13.2 - Construct a finite-state machine for lock that...Ch. 13.2 - Construct a finite-state machine for a toll...Ch. 13.2 - Construct a finite-state machine for entering a...Ch. 13.2 - Construct a finite-state machine for a restricted...Ch. 13.2 - Construct a finite-state machine that gives an...Ch. 13.2 - Prob. 17ECh. 13.2 - Construct a finite-state machine that determines...Ch. 13.2 - Construct a finite-state machine that determines...Ch. 13.2 - Prob. 20ECh. 13.2 - Prob. 21ECh. 13.2 - Find the output string generated by the Moore...Ch. 13.2 - Prob. 23ECh. 13.2 - Construct a Moore machine that gives an output of...Ch. 13.2 - Prob. 25ECh. 13.3 - Prob. 1ECh. 13.3 - 2. Show that if A is a set of strings, then.
Ch. 13.3 - Find all pairs of sets of strings A and B for...Ch. 13.3 - Show that these equalities hold. a) {}*={} b)...Ch. 13.3 - Prob. 5ECh. 13.3 - Prob. 6ECh. 13.3 - Prob. 7ECh. 13.3 - Prob. 8ECh. 13.3 - Prob. 9ECh. 13.3 - Determine whether the string 01001 is in each of...Ch. 13.3 - Determine whether each of these strings is...Ch. 13.3 - Determine whether each of these strings is...Ch. 13.3 - Determine whether all the strings in each of these...Ch. 13.3 - Show that if M=(S,I,f,so,F) is a deterministic...Ch. 13.3 - Given a finite-state automaton M=(S,I,f,so,F) ,...Ch. 13.3 - In Exercises 16—22 find the language recognized by...Ch. 13.3 - In Exercises 16—22 find the language recognized by...Ch. 13.3 - Prob. 18ECh. 13.3 - Prob. 19ECh. 13.3 - In Exercises 16—22 find the language recognized by...Ch. 13.3 - In Exercises 16—22 find the language recognized by...Ch. 13.3 - Prob. 22ECh. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Prob. 27ECh. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Prob. 29ECh. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Construct a deterministic finite-state automaton...Ch. 13.3 - Prob. 33ECh. 13.3 - Prob. 34ECh. 13.3 - Prob. 35ECh. 13.3 - Prob. 36ECh. 13.3 - Prob. 37ECh. 13.3 - Prob. 38ECh. 13.3 - Prob. 39ECh. 13.3 - Use Exercise 39 finite-state automata constructed...Ch. 13.3 - Prob. 41ECh. 13.3 - Prob. 42ECh. 13.3 - Prob. 43ECh. 13.3 - Prob. 44ECh. 13.3 - Prob. 45ECh. 13.3 - In Exercises 43-49 find the language recognized by...Ch. 13.3 - Prob. 47ECh. 13.3 - In Exercises 43-49 find the language recognized by...Ch. 13.3 - Prob. 49ECh. 13.3 - Find a deterministic finite-state automaton that...Ch. 13.3 - Prob. 51ECh. 13.3 - Find a deterministic finite-state automaton that...Ch. 13.3 - Find a deterministic finite-state automaton that...Ch. 13.3 - Find a deterministic finite-state automaton that...Ch. 13.3 - Find a deterministic finite-state automaton that...Ch. 13.3 - Find a nondeterministic finite-state automaton...Ch. 13.3 - Prob. 57ECh. 13.3 - Prob. 58ECh. 13.3 - Prob. 59ECh. 13.3 - Prob. 60ECh. 13.3 - Prob. 61ECh. 13.3 - Prob. 62ECh. 13.4 - Describe in words the strings in each of these...Ch. 13.4 - Prob. 2ECh. 13.4 - Prob. 3ECh. 13.4 - Prob. 4ECh. 13.4 - Express each of these sets using a regular...Ch. 13.4 - Express each of these sets using a regular...Ch. 13.4 - Express each of these sets using a regular...Ch. 13.4 - Construct deterministic finite-state automata that...Ch. 13.4 - Construct nondeterministic finite-state automata...Ch. 13.4 - Construct nondeterministic finite-state automata...Ch. 13.4 - Show that if A is a regular set, then AR, the set...Ch. 13.4 - Using the construction described in the proof of...Ch. 13.4 - Using the construction described in the proof of...Ch. 13.4 - Construct a nondeterministic finite-state...Ch. 13.4 - In Exercises 15-17 conflict a regular grammar...Ch. 13.4 - In Exercises 15-17 conflict a regular grammar...Ch. 13.4 - In Exercises 15-17 conflict a regular grammar...Ch. 13.4 - Show that the finite-state automaton constructed...Ch. 13.4 - Show that the regular grammar constructed from a...Ch. 13.4 - Show that every nondeterministic finite-state...Ch. 13.4 - Let M=(S,I,f,s0,F) be a deterministic finite-state...Ch. 13.4 - One important technique used to prove that certain...Ch. 13.4 - Show that the set 02n1nn=0,1,2,... is not regular...Ch. 13.4 - Show that the set {1n2n=0,1,2,...} is not regular...Ch. 13.4 - Show that the set of palindromes over {0, 1} is...Ch. 13.4 - Prob. 26ECh. 13.4 - Prob. 27ECh. 13.4 - Prob. 28ECh. 13.4 - Prob. 29ECh. 13.4 - Prob. 30ECh. 13.4 - Use Exercise 29 to show that the language...Ch. 13.5 - Let T be the Turing machine defined by the...Ch. 13.5 - Let T be the Turing machine defined by the...Ch. 13.5 - What does the Turing machine defined by the...Ch. 13.5 - What does the Turing machine described by the...Ch. 13.5 - What does the Turing machine described by the...Ch. 13.5 - Construct a Turing machine with tape 0, 1, and B...Ch. 13.5 - Construct a Turning machine with tape symbols 0,...Ch. 13.5 - Construct a Turing machine with tape symbols 0, 1,...Ch. 13.5 - Construct a Turing machine with tape symbols 0, 1,...Ch. 13.5 - Construct a Turing machine with tape symbols 0, 1,...Ch. 13.5 - Construct a Turing machine that recognizes the set...Ch. 13.5 - Construct a Turing machine that recognizes the set...Ch. 13.5 - Construct a Turing machine that recognizes the set...Ch. 13.5 - Show at each step the contents of the tape of the...Ch. 13.5 - Explain why the Turing machine in Example 3...Ch. 13.5 - Construct a Turing machine that recognizes the set...Ch. 13.5 - Construct a Turing machine that recognizes the set...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turing machine that computes the...Ch. 13.5 - Construct a Turning machine that computes the...Ch. 13.5 - Prob. 27ECh. 13.5 - Prob. 28ECh. 13.5 - Which of the following problems is a decision...Ch. 13.5 - Which of the following problems is a decision...Ch. 13.5 - Prob. 31ECh. 13.5 - Show that the function B(n) cannot be computed by...Ch. 13 - a) Define a phrase-structure grammar. b) What does...Ch. 13 - a) What is the language generated by a...Ch. 13 - Prob. 3RQCh. 13 - Prob. 4RQCh. 13 - Prob. 5RQCh. 13 - a) What is a finite-state machine? b) Show how a...Ch. 13 - Prob. 7RQCh. 13 - Prob. 8RQCh. 13 - Prob. 9RQCh. 13 - Prob. 10RQCh. 13 - a) Define a nondeterministic finite-state...Ch. 13 - a) Define the set of regular expressions over a...Ch. 13 - Prob. 13RQCh. 13 - Prob. 14RQCh. 13 - Prob. 15RQCh. 13 - Prob. 16RQCh. 13 - Describe how Turing machines are used to recognize...Ch. 13 - Prob. 18RQCh. 13 - Prob. 19RQCh. 13 - Prob. 1SECh. 13 - Prob. 2SECh. 13 - Prob. 3SECh. 13 - Prob. 4SECh. 13 - Prob. 5SECh. 13 - Prob. 6SECh. 13 - Prob. 7SECh. 13 - Prob. 8SECh. 13 - Prob. 9SECh. 13 - Prob. 10SECh. 13 - Prob. 11SECh. 13 - Prob. 12SECh. 13 - Prob. 13SECh. 13 - Construct a finite-state machine with output that...Ch. 13 - Construct a finite-state machine with output that...Ch. 13 - Prob. 16SECh. 13 - Prob. 17SECh. 13 - Prob. 18SECh. 13 - Construct a deterministic finite-state automaton...Ch. 13 - Prob. 20SECh. 13 - Prob. 21SECh. 13 - Prob. 22SECh. 13 - Prob. 23SECh. 13 - Prob. 24SECh. 13 - Prob. 25SECh. 13 - Show that {02nnN} is not regular. You may use the...Ch. 13 - Prob. 27SECh. 13 - Prob. 28SECh. 13 - Construct a Turing machine that computes the...Ch. 13 - Prob. 30SECh. 13 - Prob. 1CPCh. 13 - Prob. 2CPCh. 13 - Prob. 3CPCh. 13 - Prob. 4CPCh. 13 - Given the state table of a Moore machine and an...Ch. 13 - Given the state table of a Mealy machine and an...Ch. 13 - Given the state table of a deterministic...Ch. 13 - Prob. 8CPCh. 13 - Prob. 9CPCh. 13 - Prob. 10CPCh. 13 - Given a regular grammar, construct a finite-state...Ch. 13 - Given a finite-state automaton, construct a...Ch. 13 - Prob. 13CPCh. 13 - Solve the busy beaver problem for two states by...Ch. 13 - Prob. 2CAECh. 13 - Prob. 3CAECh. 13 - Prob. 4CAECh. 13 - Prob. 5CAECh. 13 - Prob. 1WPCh. 13 - Describe the Backus-Naur form (and extended...Ch. 13 - Explain how finite-state machines are used by...Ch. 13 - Explain how finite-state machines are used in the...Ch. 13 - Explain how finite-state machines are used in...Ch. 13 - Compare the use of Moore machines versus Mealy...Ch. 13 - Explain the concept of minimizing finite-state...Ch. 13 - Give the definition of cellular automata, Explain...Ch. 13 - Define a pushdown automaton. Explain how pushdown...Ch. 13 - Define a linear-bounded automaton. Explain how...Ch. 13 - Prob. 11WPCh. 13 - Prob. 12WPCh. 13 - Prob. 13WPCh. 13 - Show that a Turing machine can simulate any action...Ch. 13 - Prob. 15WPCh. 13 - Describe the basic concepts of the lambda-calculus...Ch. 13 - Show that a Turing machine as defined in this...Ch. 13 - Prob. 18WP
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.Similar questions
- 3. Let 4 0 0 00 0 0 1.2 0 00 0 0 0 -10.1 0 0 0 D = 0 0 0 00 0 0 0 0 05 0 0 0 0 0 0 2.8 Either explicitly compute D-¹ or explain why it doesn't exist.arrow_forward4. [9 points] Assume that B, C, E are all 3 x 3 matrices such that BC == -64 -1 0 3 4 4 4 -2 2 CB=-1-2 4 BE -2 1 3 EC = 1 3 2 -7, 1 6 -6 2-5 -7 -2 Explicitly compute the following by hand. (I.e., write out the entries of the 3 × 3 matrix.) (a) [3 points] B(E+C) (b) [3 points] (E+B)C (c) [3 points] ETBTarrow_forward6. Consider the matrices G = 0 (3) -3\ -3 2 and H = -1 2 0 5 0 5 5 noting that H(:, 3) = 2H(:,1) + H(:, 2). Is G invertible? Explain your answer. Is H invertible? Explain your answer. Use co-factor expansion to find the determinant of H. (Hint: expand the 2nd or 3rd row)arrow_forward
- B3 Consider X ~ Bern(p) (a) Find Mx(t), the moment generating function of X. iid (b) If X1,..., Xn Bern(p), find the MGF, say My (t) of n Y = ΣΧ (c) Using the fact that i=1 n lim (1 (1+2)"= N→X = e² find limn→∞ My (t) in the case that p satisfies limn→∞ np = λ, say. (d) State the distribution of Y in the case that n is not large, and the distribution of Y in the limiting case described in the question.arrow_forwardB1 The density of the x2 distribution is given in the notes as 1 F(§)2/2 (x)=()2/21 x/2-1/2, if x > 0, and e where I(t)=√xt-¹e dx is the gamma function. otherwise, Find the point at which o(a) has its maximum, i.e. find arg max, o, (x)arrow_forwardFor the matrix A = = ( 6 }) . explicitly compute by hand (with work shown) the following. I2A, where I2 is the 2 × 2 identity matrix. A-1 solving the following linear systems by using A-¹: c+y= 1 y = 1 (d) (e) (f) A² find the diagonal entries of Aarrow_forward
- If 3x−y=12, what is the value of 8x / 2y A) 212B) 44C) 82D) The value cannot be determined from the information given.arrow_forwardC=59(F−32) The equation above shows how temperature F, measured in degrees Fahrenheit, relates to a temperature C, measured in degrees Celsius. Based on the equation, which of the following must be true? A temperature increase of 1 degree Fahrenheit is equivalent to a temperature increase of 59 degree Celsius. A temperature increase of 1 degree Celsius is equivalent to a temperature increase of 1.8 degrees Fahrenheit. A temperature increase of 59 degree Fahrenheit is equivalent to a temperature increase of 1 degree Celsius. A) I onlyB) II onlyC) III onlyD) I and II onlyarrow_forwardplease answer the questions below ands provide the required codes in PYTHON. alsp provide explanation of how the codes were executed. Also make sure you provide codes that will be able to run even with different parameters as long as the output will be the same with any parameters given. these questions are not graded. provide accurate codes pleasearrow_forward
- (1) Let F be a field, show that the vector space F,NEZ* be a finite dimension. (2) Let P2(x) be the vector space of polynomial of degree equal or less than two and M={a+bx+cx²/a,b,cЄ R,a+b=c),show that whether Mis hyperspace or not. (3) Let A and B be a subset of a vector space such that ACB, show that whether: (a) if A is convex then B is convex or not. (b) if B is convex then A is convex or not. (4) Let R be a field of real numbers and X=R, X is a vector space over R show that by definition the norms/II.II, and II.112 on X are equivalent where Ilxll₁ = max(lx,l, i=1,2,...,n) and llxll₂=(x²). oper (5) Let Ⓡ be a field of real numbers, Ⓡis a normed space under usual operations and norm, let E=(2,5,8), find int(E), b(E) and D(E). (6) Write the definition of bounded linear function between two normed spaces and write with prove the relation between continuous and bounded linear function between two normed spaces.arrow_forwardind → 6 Q₁/(a) Let R be a field of real numbers and X-P(x)=(a+bx+cx²+dx/ a,b,c,dER},X is a vector space over R, show that is finite dimension. (b) Let be a bijective linear function from a finite dimension vector ✓ into a space Yand Sbe a basis for X, show that whether f(S) basis for or not. (c) Let be a vector space over a field F and A,B)affine subsets of X,show that whether aAn BB, aAU BB be affine subsets of X or not, a,ẞ EF. (12 Jal (answer only two) (6) Let M be a non-empty subset of a vector space X and tEX, show that M is a hyperspace of X iff t+M is a hyperplane of X and tЄt+M. (b) State Jahn-Banach theorem and write with prove an application of Hahn-arrow_forward(b) Let A and B be two subset of a linear space X such that ACB, show that whether if A is affine set then B affine or need not and if B affine set then A affine set or need not. Qz/antonly be a-Show that every hyperspace of a vecor space X is hyperplane but the convers need not to be true. b- Let M be a finite dimension subspace of a Banach space X show that M is closed set. c-Show that every two norms on finite dimension vector space are equivant (1) Q/answer only two a-Write the definition of bounded set in: a normed space and write with prove an equivalent statement to a definition. b- Let f be a function from a normed space X into a normed space Y, show that f continuous iff f is bounded. c-Show that every finite dimension normed space is a Banach. Q/a- Let A and B two open sets in a normed space X, show that by definition AnB and AUB are open sets. (1 nood truearrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
Linear Algebra: A Modern IntroductionAlgebraISBN:9781285463247Author:David PoolePublisher:Cengage Learning
Elements Of Modern AlgebraAlgebraISBN:9781285463230Author:Gilbert, Linda, JimmiePublisher:Cengage Learning,
Algebra: Structure And Method, Book 1AlgebraISBN:9780395977224Author:Richard G. Brown, Mary P. Dolciani, Robert H. Sorgenfrey, William L. ColePublisher:McDougal Littell
Linear Algebra: A Modern Introduction
Algebra
ISBN:9781285463247
Author:David Poole
Publisher:Cengage Learning
Elements Of Modern Algebra
Algebra
ISBN:9781285463230
Author:Gilbert, Linda, Jimmie
Publisher:Cengage Learning,
Algebra: Structure And Method, Book 1
Algebra
ISBN:9780395977224
Author:Richard G. Brown, Mary P. Dolciani, Robert H. Sorgenfrey, William L. Cole
Publisher:McDougal Littell
Finite State Machine (Finite Automata); Author: Neso Academy;https://www.youtube.com/watch?v=Qa6csfkK7_I;License: Standard YouTube License, CC-BY
Finite State Machine (Prerequisites); Author: Neso Academy;https://www.youtube.com/watch?v=TpIBUeyOuv8;License: Standard YouTube License, CC-BY