- 12.3.1: Consider the finite-state automaton A given by the following transi...
- 12.3.2: Consider the finite-state automaton A given by the following transi...
- 12.3.3: Consider the finite-state automaton A discussed in Example 12.3.1:
- 12.3.4: If A is a finite-state automaton, then for some integer K 0, the se...
- 12.3.5: Consider the finite-state automaton given by the following transiti...
- 12.3.6: Consider the finite-state 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 finite-state automaton are k-equivale...
- 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 Finite-State Automata
Full solutions for Discrete Mathematics with Applications | 4th Edition
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).
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 n-l - An).
Diagonalizable matrix A.
Must have n independent eigenvectors (in the columns of S; automatic with n different eigenvalues). Then S-I AS = A = eigenvalue matrix.
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.
Invert A by row operations on [A I] to reach [I A-I].
Identity matrix I (or In).
Diagonal entries = 1, off-diagonal entries = 0.
Incidence matrix of a directed graph.
The m by n edge-node incidence matrix has a row for each edge (node i to node j), with entries -1 and 1 in columns i and j .
A symmetric matrix with eigenvalues of both signs (+ and - ).
Inverse matrix A-I.
Square matrix with A-I A = I and AA-l = 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 B-1 A-I and (A-I)T. Cofactor formula (A-l)ij = Cji! detA.
Linear combination cv + d w or L C jV j.
Vector addition and scalar multiplication.
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.
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·