Errata For First Printing Of Automata Computability And Complexity Theory And Applications 4t54z

Errata for First Printing of Automata, Computability, and Complexity: Theory and Applications Page 2 17 20

Location Line 3 Example 2.16 Exercise 6.c.

24

Example 3.5

36 49

First bullet Line2

50

Example 4.12

55

64 65

FSM diagram Figure in Example 5.6 Figure in Example 5.10 Example 5.10 Line 3

66

Line -9

82

Halfway down the page

82 88 101 112

Line -13 Last line Soundex diagram Last line

114

Line -9

61 64

121 122

First line of third paragraph Exercise 1 Exercise 2j

124

Exercise 11d

133-134

Proof of Thm. 6.1

118

136 142

Final figure in Example 6.5 Line 11

Error We don’t we just … => Why don’t we just … This answer isn't right. It describes a superset of L*. Add ) before final } Add + to produce "each of the substrings … is an element of {0, 1, 2, 3, 4, 5, 6, 7, 8, 9)+ …" Should be “define problems as languages to be decided”. Change “w elementof c*” to “w elementof {c}*”. Add comma after "some function f". Change two instances of "counter example" to "counterexample" Each transition labeled D should advance two states. The dead state (labeled d) should not be accepting. The state labeled U should be labeled O. The loop back to it should be labeled Sigma - {u} The word "sacrilegious" is not in L - the letters are out of order. Change "an FSM" to "a DFSM". “A subset-of is the set of final states” should be, “A subset-of K is a set of accepting states”. The two lines of code “st = st1.” and “If st = emptyset then exit.” should be moved to the left so that they line up with “For all q in st do:”. Keep the /* parts lined up as they are. In the argument to big-O, change “w” to “|w|”. Change “we can us it” to “we can use it”. Add an arrow to the edge from state 2v back to itself. Remove space before closing ). ".. just prior to reading a fifth output symbol." Should be ".. just prior to generating a fifth output symbol." "This new machine is indeed nondeterministic ..." should be "This new machine is indeed deterministic ...". Make state 5 nonaccepting. Change “as a substrings” to “as substrings”. The R in wwR should not be italicized (but it is correct to be a superscript). Change every instance of lower case delta to upper case delta. (Two on p. 133 and 14 on p. 134) The state with in-transition labeled a should not be accepting. In the definition of M, change lower case delta to upper case

153 154 165 174 174 195 208, 209, 210, 213, 216, 217, 220, 222, 223, 225, 226, 227, 228, 230 210 215 220 235 246 249 264 281 282 308 310

Delta. Two errors in the transition diagram: Label the arc from q2 to Exercise 9 q0 a. Make state q3 nonaccepting. In the transition diagram, the arc from q1 to q3 should have the Exercise 15 single label b. Paragraph should end with, "... and accepts all strings that M1 Line -13 rejects." Line 7 Remove ) after "some p". First line of Example The R in wwR should not be italicized (but it is correct to be a 8.11 superscript). Remove blank between w and , Also remove extra blank after Line -2 the second w

Formal definition of Quadruple should start with ( and end with ). Some examples grammar use { and }. Some use { and } now.

First line of Example The R in wwR should not be italicized (but it is correct to be a 11.3 superscript). Step 5 of the Change “from VG'" to “from VG' - ΣG'". algorithm In the left-most derivation, the four instances of "The" should The derivations be "the". In the right-most one, the single instance of "The" should be "the". Line -4 Section 11.7.4 should be 11.7.3. Problem 6.a Remove the word “where” just after the colon. Lines 14-15 Change "M is a sex-tuple" to "M is a six-tuple". Line 2 The first rule should be F -> (E). Figure 13.1 The caption is chopped off at the bottom. It should say "yield". Line 17 Remove the space between “w” and “,”. First and third lines The R in wwR should not be italicized (but it is correct to be a of Example 13.15 superscript). Problem 1.t. The last two *’s are superscripted. They shouldn’t be.

312 315 319 354 355 356

380 386 389 402 402 419 438 443 454 455 459 460 465 468 468 475 479 480-1

Problem 12.a, second line Line -13

Change "regular (but not context free), context free or neither" to "regular, context-free (but not regular) or neither". “is O(n2^n)” should be “is O(ng^2n)”. “string could have been pumped” should be “characters could Line -12 have been pumped”. First chart Get rid of the top row (labeled 4). Second chart Add "V, N" above the caption "saw" (as in the chart above it). Second row (counting down from the top): Move VP to the right so it aligns with VP on row 6. Third row: Move NP to the Second chart right so it aligns with NP on row 5. Fourth row: Move ProperNoun to the right so it aligns with NP on row 5. Example 17.11: Delete the blank that occurs immediately after writing x the Diagram of machine first time. So after writing x, the code is: L to a blank, L to a C blank, write x, loop back. Part (b) of Figure Row 3, last separated column: Put a blank in the empty square. 17.3 Tree in Figure 17.4 Label on root of tree: the "S" should be "s". Line 3 of the second In column 2, change "q10” to "h10". table Last line of Example Change "q10” to "h10". 17.20 Line 20, step 1.1 Remove space between w and period. Proof of Theorem Change "(by Theorem 2.2)" to "(by Theorem 2.3)". 20.3 Proof of Theorem Add special case in which L is finite. 20.9 Line 2 Change “Section 21.2” to “Section 21.6”. Last four lines of Change five instances of "x" to "s" step 3 of algorithm Last line of Fill in the first empty column with b [4]. Then shift the dovetailing table in rightmost three columns one to the left. middle of page First line Change element-of symbol to not-element-of symbol. Second bullet in Change “H: does not halt …” to “H: M does not halt …”. proof Line -11 Change "machhnes" to "machines". Line -6 Change "Riae's Theorem" to "Rice's Theorem". Title of Theorem In "Is M …", italicize "M". 21.14 Line 8 1.2. should be 1.1. Continuation of Continue the margin rule that marks theorems all the way to

483 485 490 491 533 542 542 564 627

Theorem 21.18 Exercise 1.n. Exercise 18 Example 22.2, first row of the tree, rightmost branch Last line of definition of M_P Line -3 TM description in middle of page Line 20 TM description in middle of page Line -2

631 648

Tree in Example 28.1 Footnote Line 10

664

Line 5 of proof

675 733 742 743

Line 13 Line -15 Line -7 Line 9 First line of Table A.1 Last line Title of Example A.17 Title of Example A.19 Line 2 Step 2 of the algorithm Line 3 Line -14 Line -4

629

746 765 782 784 785 842 853 853 855

just before the Section 21.6.3 heading. "{a*}" should be "a*". "doubly reducible" should be bold italic. There should be three x’s, so add one under the first 0/1 column. Should say, "halt and accept". Change “G does almost of its work …” to “G does almost all of its work …”. Change two instance of L to q to L to blank. Insert [ before CATEGORY NP. Change two instance of L to q to L to blank. Change “It should now by obvious” to “It should now be obvious”. The line between 1 and 5 should not be in bold. Change Corman to Cormen. Change "is likely to exit" to "is likely to exist". Change " " to " " and change " " to " ". Change "no repeated edges" to "no repeated vertices". Get rid of word to before the quoted expression "to find". Change Corman to Cormen. Change Corman to Cormen. Change first instance of P "and symbol" Q to P "or symbol" Q. Change “symmetric” to “transitive”. The n in n-squared should not be bold. Change "Tolens" to "Tollens". The first i on the line should not be subscripted. Change "whose left-hand sides" to "whose left-hand side". Insert } after ). Insert "the" to produce "string that is the yield …" Insert space after bullet.

874

Line 9

921

Figure I.5

955

Line 12

986

Last bullet item

1009

Line 5

1016

Line -9 and -11

1056 1075

Line -2 Line -3 middle of second 1088 column back cover Line 7 after title

Nuke subscript 1 after f. In the Receiver diagram, remove the unlabeled arc that goes from Replying to Active. Change "<M, w>" to "<M>". Change "halt on w" to "halt on epsilon". (Use the symbol for epsilon.) Change "Regular grammars to not ..." to "Regular grammars do not ...". Delete the ) immediately to the left of the implication arrow. Insert a period after each statement (before the /* part), as in Line -12. “orlog” should be “orloj”. Change Corman to Cormen. Change Corman to Cormen. “theproblem” should be “the problem”.