 12.3.1: Consider the finitestate automaton A given by the following transi...
 12.3.2: Consider the finitestate automaton A given by the following transi...
 12.3.3: Consider the finitestate automaton A discussed in Example 12.3.1:
 12.3.4: If A is a finitestate automaton, then for some integer K 0, the se...
 12.3.5: Consider the finitestate automaton given by the following transiti...
 12.3.6: Consider the finitestate automaton given by the following transiti...
 12.3.7: Are the automata A and A$ shown below equivalent?
 12.3.8: Are the automata A and A$ shown below equivalent?
 12.3.9: Are the automata A and A$ shown below equivalent?
 12.3.10: Are the automata A and A$ shown below equivalent?
 12.3.11: Prove property (12.3.1).
 12.3.12: How should the proof of property (12.3.1) be modified to prove prop...
 12.3.13: Prove property (12.3.3). 14. Prove property (12.3.4)
 12.3.14: Prove property (12.3.4).
 12.3.15: Prove property (12.3.5).
 12.3.16: Prove property (12.3.6).
 12.3.17: Prove that if two states of a finitestate automaton are kequivale...
 12.3.18: Write a complete proof of property (12.3.7).
 12.3.19: Write a complete proof of property (12.3.8).
Solutions for Chapter 12.3: Simplifying FiniteState Automata
Full solutions for Discrete Mathematics with Applications  4th Edition
ISBN: 9780495391326
Solutions for Chapter 12.3: Simplifying FiniteState Automata
Get Full SolutionsChapter 12.3: Simplifying FiniteState Automata includes 19 full stepbystep solutions. This textbook survival guide was created for the textbook: Discrete Mathematics with Applications , edition: 4. Since 19 problems in chapter 12.3: Simplifying FiniteState Automata have been answered, more than 51466 students have viewed full stepbystep solutions from this chapter. Discrete Mathematics with Applications was written by and is associated to the ISBN: 9780495391326. This expansive textbook survival guide covers the following chapters and their solutions.

Column picture of Ax = b.
The vector b becomes a combination of the columns of A. The system is solvable only when b is in the column space C (A).

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).

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

Elimination.
A sequence of row operations that reduces A to an upper triangular U or to the reduced form R = rref(A). Then A = LU with multipliers eO in L, or P A = L U with row exchanges in P, or E A = R with an invertible E.

Free columns of A.
Columns without pivots; these are combinations of earlier columns.

GaussJordan method.
Invert A by row operations on [A I] to reach [I AI].

Identity matrix I (or In).
Diagonal entries = 1, offdiagonal entries = 0.

Incidence matrix of a directed graph.
The m by n edgenode incidence matrix has a row for each edge (node i to node j), with entries 1 and 1 in columns i and j .

Indefinite matrix.
A symmetric matrix with eigenvalues of both signs (+ and  ).

Inverse matrix AI.
Square matrix with AI A = I and AAl = I. No inverse if det A = 0 and rank(A) < n and Ax = 0 for a nonzero vector x. The inverses of AB and AT are B1 AI and (AI)T. Cofactor formula (Al)ij = Cji! detA.

Linear combination cv + d w or L C jV j.
Vector addition and scalar multiplication.

Lucas numbers
Ln = 2,J, 3, 4, ... satisfy Ln = L n l +Ln 2 = A1 +A~, with AI, A2 = (1 ± /5)/2 from the Fibonacci matrix U~]' Compare Lo = 2 with Fo = O.

Nilpotent matrix N.
Some power of N is the zero matrix, N k = o. The only eigenvalue is A = 0 (repeated n times). Examples: triangular matrices with zero diagonal.

Particular solution x p.
Any solution to Ax = b; often x p has free variables = o.

Pascal matrix
Ps = pascal(n) = the symmetric matrix with binomial entries (i1~;2). Ps = PL Pu all contain Pascal's triangle with det = 1 (see Pascal in the index).

Plane (or hyperplane) in Rn.
Vectors x with aT x = O. Plane is perpendicular to a =1= O.

Rayleigh quotient q (x) = X T Ax I x T x for symmetric A: Amin < q (x) < Amax.
Those extremes are reached at the eigenvectors x for Amin(A) and Amax(A).

Simplex method for linear programming.
The minimum cost vector x * is found by moving from comer to lower cost comer along the edges of the feasible set (where the constraints Ax = b and x > 0 are satisfied). Minimum cost at a comer!

Sum V + W of subs paces.
Space of all (v in V) + (w in W). Direct sum: V n W = to}.

Triangle inequality II u + v II < II u II + II v II.
For matrix norms II A + B II < II A II + II B II·