DM565 - Formal Languages and Data Processing
 
Fall 2023
Kim Skak Larsen

Home Innovation

My Supplementary Errata to Sipser
See the literature page for the Sipser book home page and the errata published by the author. The comments below, are my suggestions for supplementary adjustments.

Page 41, Example 1.17

I think the definition of L(M5) is too informal and operational, and suggest

L(M5) = { w | the sum of the symbols in the longest postfix of w with no occurrences of ⟨RESET⟩ is 0 modulo 3}

Page 55, Proof

For N, I think the alphabet ought to be Σε.

Page 60, Item 1

It's of course a trade-off between formality and unnecessary clutter, but maybe here or in the proof idea it could say that state names don't matter and we can assume that everything is disjoint, i.e., Q1, Q2, and {q0}.

Page 69, Example 1.58

It is implicitly used that concatenation is associative, but that has not been shown or discussed.

Page 70, Third bullet

It follows if bullets above have higher priority, but since start and accept states are explicitly exempted, I think that should also be done further on in the sentence:

Except for the start and accept states, one arrow goes from every state to every other state except the start state and also from each state to itself.

Page 72, Figure 1.63

At first, one thinks one gets a complete picture of the three states in the GNFA. However, that's not the case, and I think the following would help:

We only show what is necessary for the transformation, leaving out other states, but also the arrows from qi and qj to themselves.

I believe that would help readers who are used to seeing concepts such induced subgraphs, for instance.

Page 161, Selected Solution 2.8

The very last word in that selected solution should be him; not her.

 


   Data protection at SDUDatabeskyttelse på SDU