 12.3.12.3.1: Let A = to, 1 1 } and B = {00, 01}. Find each of these sets. a) AB
 12.3.12.3.2: Show that if A is a set of strings, then A0 = 0A = 0.
 12.3.12.3.3: Find all pairs of sets of strings A and B for which AB = { l 0, Ill...
 12.3.12.3.4: Show that these equalities hold. a) {A}* = {A} b) (A*)* = A* for ev...
 12.3.12.3.5: Describe the elements of the set A * for these values of A. a) { l ...
 12.3.12.3.6: Let V be an alphabet, and let A and B be subsets of V*. Show that I...
 12.3.12.3.7: Let V be an alphabet, and let A and B be subsets of V* with A B. Sh...
 12.3.12.3.8: Suppose that A is a subset of V*, where V is an alphabet. Prove or ...
 12.3.12.3.9: Determine whether the string 111 01 is in each of these sets. a) {O...
 12.3.12.3.10: Determine whether the string 01001 is in each of these sets. a) to,...
 12.3.12.3.11: Determine whether each of these strings is recognized by the determ...
 12.3.12.3.12: Determine whether each of these strings is recognized by the determ...
 12.3.12.3.13: Determine whether all the strings in each of these sets are recogni...
 12.3.12.3.14: Show that if M = (S, /, f, so, F) is a deterministic finitestate au...
 12.3.12.3.15: Given a deterministic finitestate automaton M = (S, /, f, so, F), ...
 12.3.12.3.16: In Exercises 1622 find the language recognized by the given determ...
 12.3.12.3.17: In Exercises 1622 find the language recognized by the given determ...
 12.3.12.3.18: In Exercises 1622 find the language recognized by the given determ...
 12.3.12.3.19: In Exercises 1622 find the language recognized by the given determ...
 12.3.12.3.20: In Exercises 1622 find the language recognized by the given determ...
 12.3.12.3.21: In Exercises 1622 find the language recognized by the given determ...
 12.3.12.3.22: In Exercises 1622 find the language recognized by the given determ...
 12.3.12.3.23: Construct a deterministic finitestate automaton that recognizes th...
 12.3.12.3.24: Construct a deterministic finitestate automaton that recognizes th...
 12.3.12.3.25: Construct a deterministic finitestate automaton that recognizes th...
 12.3.12.3.26: Construct a deterministic finitestate automaton that recognizes th...
 12.3.12.3.27: Construct a deterministic finitestate automaton that recognizes th...
 12.3.12.3.28: Construct a deterministic finitestate automaton that recognizes th...
 12.3.12.3.29: Construct a deterministic finitestate automaton that recognizes th...
 12.3.12.3.30: Construct a deterministic finitestate automaton that recognizes th...
 12.3.12.3.31: Construct a deterministic finitestate automaton that recognizes th...
 12.3.12.3.32: Construct a deterministic finitestate automaton that recognizes th...
 12.3.12.3.33: Construct a deterministic finitestate automaton that recognizes th...
 12.3.12.3.34: Construct a deterministic finitestate automaton that recognizes th...
 12.3.12.3.35: Construct a finitestate automaton that recognizes the set of bit s...
 12.3.12.3.36: Construct a finitestate automaton with four states that recognizes...
 12.3.12.3.37: Show that there is no finitestate automaton with two states that r...
 12.3.12.3.38: Show that there is no finitestate automaton with three states that...
 12.3.12.3.39: Explain how you can change the deterministic finitestate automaton...
 12.3.12.3.40: Use Exercise 39 and finitestate automata constructed in Example 6 ...
 12.3.12.3.41: Use the procedure you described in Exercise 39 and the finitestate...
 12.3.12.3.42: Use the procedure you described in Exercise 39 and the finitestate...
 12.3.12.3.43: In Exercises 4349 find the language recognized by the given nondet...
 12.3.12.3.44: In Exercises 4349 find the language recognized by the given nondet...
 12.3.12.3.45: In Exercises 4349 find the language recognized by the given nondet...
 12.3.12.3.46: In Exercises 4349 find the language recognized by the given nondet...
 12.3.12.3.47: In Exercises 4349 find the language recognized by the given nondet...
 12.3.12.3.48: In Exercises 4349 find the language recognized by the given nondet...
 12.3.12.3.49: In Exercises 4349 find the language recognized by the given nondet...
 12.3.12.3.50: Find a deterministic finitestate automaton that recognizes the sam...
 12.3.12.3.51: Find a deterministic finitestate automaton that recognizes the sam...
 12.3.12.3.52: Find a deterministic finitestate automaton that recognizes the sam...
 12.3.12.3.53: Find a deterministic finitestate automaton that recognizes the sam...
 12.3.12.3.54: Find a deterministic finitestate automaton that recognizes the sam...
 12.3.12.3.55: Find a deterministic finitestate automaton that recognizes each of...
 12.3.12.3.56: Find a nondeterministic finitestate automaton that recognizes each...
 12.3.12.3.57: Show that there is no finitestate automaton that recognizes the se...
 12.3.12.3.58: a) Show that for every nonnegative integer k, Rk is an equivalence ...
 12.3.12.3.59: Show that there is a nonnegative integer n such that the set of ne...
 12.3.12.3.60: a) Show that s arid t are Oequivalent if and only if either both s...
 12.3.12.3.61: a) Show that if M is a finitestate automaton, then the quotient au...
 12.3.12.3.62: Answer these questions about the finitestate automaton M shown her...
Solutions for Chapter 12.3: Modeling Computation
Full solutions for Discrete Mathematics and Its Applications  6th Edition
ISBN: 9780073229720
Solutions for Chapter 12.3: Modeling Computation
Get Full SolutionsDiscrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073229720. Since 62 problems in chapter 12.3: Modeling Computation have been answered, more than 33834 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. Chapter 12.3: Modeling Computation includes 62 full stepbystep solutions. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 6.

Affine transformation
Tv = Av + Vo = linear transformation plus shift.

Associative Law (AB)C = A(BC).
Parentheses can be removed to leave ABC.

Column space C (A) =
space of all combinations of the columns of A.

Commuting matrices AB = BA.
If diagonalizable, they share n eigenvectors.

Companion matrix.
Put CI, ... ,Cn in row n and put n  1 ones just above the main diagonal. Then det(A  AI) = ±(CI + c2A + C3A 2 + .•. + cnA nl  An).

Complex conjugate
z = a  ib for any complex number z = a + ib. Then zz = Iz12.

Diagonalizable matrix A.
Must have n independent eigenvectors (in the columns of S; automatic with n different eigenvalues). Then SI AS = A = eigenvalue matrix.

Diagonalization
A = S1 AS. A = eigenvalue matrix and S = eigenvector matrix of A. A must have n independent eigenvectors to make S invertible. All Ak = SA k SI.

Fibonacci numbers
0,1,1,2,3,5, ... satisfy Fn = Fnl + Fn 2 = (A7 A~)I()q A2). Growth rate Al = (1 + .J5) 12 is the largest eigenvalue of the Fibonacci matrix [ } A].

Linear transformation T.
Each vector V in the input space transforms to T (v) in the output space, and linearity requires T(cv + dw) = c T(v) + d T(w). Examples: Matrix multiplication A v, differentiation and integration in function space.

Multiplication Ax
= Xl (column 1) + ... + xn(column n) = combination of columns.

Network.
A directed graph that has constants Cl, ... , Cm associated with the edges.

Pivot columns of A.
Columns that contain pivots after row reduction. These are not combinations of earlier columns. The pivot columns are a basis for the column space.

Positive definite matrix A.
Symmetric matrix with positive eigenvalues and positive pivots. Definition: x T Ax > 0 unless x = O. Then A = LDLT with diag(D» O.

Right inverse A+.
If A has full row rank m, then A+ = AT(AAT)l has AA+ = 1m.

Row picture of Ax = b.
Each equation gives a plane in Rn; the planes intersect at x.

Semidefinite matrix A.
(Positive) semidefinite: all x T Ax > 0, all A > 0; A = any RT R.

Spanning set.
Combinations of VI, ... ,Vm fill the space. The columns of A span C (A)!

Spectral Theorem A = QAQT.
Real symmetric A has real A'S and orthonormal q's.

Vandermonde matrix V.
V c = b gives coefficients of p(x) = Co + ... + Cn_IXn 1 with P(Xi) = bi. Vij = (Xi)jI and det V = product of (Xk  Xi) for k > i.