Computation Engineering: Applied Automata Theory and Logic
Book Website
1 Misc
-
Grail tool:
- The Grail tool used in various chapters is available
precompiled for Linux
here.
2 Errata
Errata as of March 27, 2007.
Recent errata added on Pages 320, 304, and 303 with respect to the Errata of March 6, 2007.
========================================
I'll often show the proposed changes by surrounding the old text by surrounded {{ }}
and the new text by [[ ]].
Page XXIII (List of Figures)
-------------------------------------------------------
Section numbers bump against figure captions (this could be a problem in
earlier pages such as XX also)
Page 12, Third line (excluding section headings)
------------------------------------------------------------------------
The study of automata theory is {{ a }} [[ ]] challenging.
Page 17, Section 2.3.2 Avoiding Contradictions
------------------------------------------------------------------------
There are many infelicities in this section. I'll show the proposed
changes by surrounding the old text by surrounded {{ }} and the new
text by [[ ]]. I enclose the entire Latex of this section. The reason
is that being too informal in this section may be misleading.
--begin
\subsection{Avoid contradictions}
\label{sec:russells-paradox}
Our first example illustrates the famous {\em Russell's Paradox}.
\index{Russell's paradox}
This paradox stems from allowing expressions such as $x\in x$ and $x\notin x$
inside characteristic formulas.
%
{{ Consider some arbitrary domain $D$. }}
[[ deleted the above sentence. ]]
{{ Define a set $S$\label{page-of-S-defn} as follows:
\[ S = \{ x\in D \;\mid\; x\notin x \}. \] }}
[[ Consider the possibility of defining a set S such that x is in S exactly
when x is not a member of x. ]]
{{ Now, the expression $x\notin x$ reveals that $x$ itself is a set. }}
[[ Delete the above. ]]
{{ Since $S$ is a set,}}
[[ If S were a set, ]]
we can now ask, ``is $S$ a member of $S$?''
\begin{list}{$\bullet$}{\addtolength{\itemsep}{-1.6\itemsep}}
\item If $S$ is a member of $S$, it cannot be in $S$, because
$S$ cannot contain sets that contain themselves.
\item However, if $S$ is not a member of $S$, then $S$ must contain
$S$!
\end{list}
%--
Contradictions are required to be complete, {\em i.e.}, apply to
all possible cases. For example, if $S\notin S$ does
not result in a contradiction, that, then, becomes a consistent
solution. In this example, we fortunately obtain a contradiction in all
the cases.
%--
The proposition $S\in S$ must produce a definite answer - true
or false. However, {\em both} answers lead to a contradiction.
We can better understand this contradiction as follows.
For Boolean quantities $a$ and $b$, let $a\Rightarrow b$ stand for
``$a$ implies $b$'' or
``if $a$ then $b$;''
in other words, $\Rightarrow$ is the {\em implication} operator.
\index{Implication}
%
Suppose $S\in S$. This allows us to conclude that $S\notin S$.
In other words, $(S\in S) \Rightarrow (S\notin S)$ is true.
In other words, $\neg (S\in S) \vee (S\notin S)$, or
$(S\notin S) \vee (S\notin S)$, or
$(S\notin S)$ is true.
Likewise, $(S\in S) \Rightarrow (S\notin S)$.
This allows us to prove $(S\in S)$ true.
Since we have proved $S\in S$ as well as $S\notin S$,
we have proved their conjunction, which is $false$!
With $false$ proved, anything else can be proved
(since $false \Rightarrow anything$ is
$\neg (false) \vee anything$, or $true$).
Therefore, it is essential to avoid contradictions in mathematics.
Russell's Paradox is used to conclude that a ``truly
\index{Set!universal}universal set'' -- a
set that contains {\em everything} -- cannot exist.
Here is how such a conclusion is drawn.
{{ Notice that set $S$, above, was defined in terms of an {\em arbitrary} set
called $D$. Now, if $D$ were to be a set that contains ``everything,''
a set such as $S$ must clearly be present inside $D$.
However, we just argued that $S$ must not exist, or else
a contradiction will result.
Consequently, a set containing {\em everything} cannot exist, for it will lack
at least $S$. }}
[[ Consider a set S defined as follows:
S \[ S = \{ x\in D \;\mid\; x\notin x \} \]
where $D$ is a completely arbitrary set.
If we now assume that S is in D, we derive a contradiction in the same
manner as illustrated earlier. Specifically, assuming $S\in D$,
$S\in S$ will lead to the conclusion $S\notin S$, and vice versa.
Now, if a universal set $U$ existed, we could use it in place of $D$ (since
$D$ is arbitrary). But then, $U$ can't be universal after all, because
if it is, it will contain $S$, leading to the above contradiction! ]]
--end
Page 19, Subtraction, Universe, Complementation, Symmetric Difference
--------------------------------------------------------------------------------------------------------------
Just some clarification.
--begin
The reference to `universal sets' here should be taken as `the least
set closed under the operations'. For example, when we say "set of
all strings over some alphabet," we mean the set generated through the
operation of concatenation of the symbols in the alphabet, starting
with the empty string epsilon.
--end
Page 26: Into function
----------------------
Into functions are 1-1, and not necessarily onto. They are injections. This should have
been clearly stated.
Page 37 onwards
----------------------
I reproduce discussions with a reviewer below.
--begin
These comments start with the material on page 37, under "3.1 Cardinality Basics",
and also has to do with some of your remarks in reference to @_1 , pp. 37-42,
and forces me, at one point, to use HTML to indicate <i>italics</i>.
(With luck, your mail-reader will INTERPRET my HTML and SHOW you the
intended italics, thus sparing you the ungainly HTML code itself.)
You write, and everyone completely agrees (once "infinite" is added),
"The smallest [infinite] cardinal number is @_0 , the next larger
cardinal number is @_1 , and so on."
But then you say:
"For now, ... @_1 is the number of elements of <i>Real</i>."
I'm not sure what bush you're beating about with that "For now,"
[[ The 'For now' may please be changed to 'Moreover' ]]
but surely it takes the Continuum Hypothesis before one can safely
assert that @_1 is the number of elements of <i>Real</i>. What IS
the number of elements of <i>Real</i> in all cases is 2^(@_0)
(as you yourself point out, essentially, under rubric 3.2.5).
Of course, as @_0 < 2^(@_0) , we must have @1 </= 2^(@_0) ; and
the Continuum Hypothesis is just the assertion that one actually
has "=" in that weak inequality, and not "<" .
(The discussion of @_0.5 , on page 42, in particular, makes
no sense, as BY DEFINITION of @_1 as the first of the cardinal
numbers > @_0 , there can NEVER be any cardinal number strictly
between @_0 and @_1 . What CH asserts, rather, is that there is no
cardinal number strictly between @_0 and 2^(@_0) , or equivalently
that 2^(@_0) IS that first one (known as @_1) after @_0 .)
[[ Page 42 must include some clarification about the way I present CH ]]
Anyway, in 3.2.5, you got it right, with 2^(@_0) = <i>Real</i> .
I turn now to your two dogs, Fifi and Howard, and the cardinalities
of their respective sets of hairs. Or rather, let me turn to the
usual coordinatized real plane.
Certainly, if we examine the points in the plane with integer
coordinates, we find these sprouting up like Fifi's hairs,
with "space" between them, and we know there are only @_0
of these particular points.
But let me draw your attention to the points whose coordinates
are RATIONAL numbers. Again there are only @_0 of these points,
but, like Howard's hairs, between any two of them one can always
find (infinitely many!) others. No need to imagine Howard has
@_1 hairs, or 2^(@_0) hairs, or the like.
Again, if we imagine that some patch of Fifi's hair can be
coordinatized by the points of the cartesian product of the
set @_1 with itself, then Fifi will have @_1 hairs, and yet
any given hair NOT at a limit-ordinal position (in one or
the other of the cordinates) will always have 8 neighbor hairs
for which: no hairs can be found strictly between
that neighbor hair and the given hair.
So: DENSITY (or non-density) of the hairs is a matter independent
of the CARDINALITY of the set of hairs.
I point this out only to help you remove the red herring that
has gotten dragged across the two poor dogs and their hairs.
[[ This would form a rather nice exercise to assign at the end of the chapter
discussing Fifi and Howard. ]]
--end
Page 48, First bullet
-------------------------------------------------------
Use P and Q, instead of A and B.
Page 55, Second bullet
-------------------------------------------------------
$R = \emptyset$ is reflexive only if the underlying set $S$ is empty.
Otherwise it is {\em not} reflexive.
Page 55, Symmetric and Related Notions
-------------------------------------------------------
One extra word `distinct' causes all the trouble and makes the definition of
asymmetric wrong.
--begin
\noindent $R$ is \index{Relation!asymmetric}
{\bf asymmetric} if there exists no two
{{ distinct }}
[[ delete word distinct ]]
$x,y\in S$ such that
$\langle x,y\rangle \in R \;\wedge\; \langle y,x\rangle \in R$.
In other words, {\bf if}
$\langle x,y\rangle \in R$, {\bf then} $\langle y,x\rangle \notin R$.
Example: ``elder brother'' is an asymmetric relation, and so is $<$ over $Nat$.
[[ Also add here: Asymmetric relations are irreflexive. ]]
--end
Page 57
-----------
Fifth bullet, last line: change the old text in {{ }} to the one in [[ ]]
in the following:
One broken journey without a short cut and one {{ without. }} [[ with. ]]
Page 60
-----------
Follow the displayed definition of R+ with this:
[[ R+ is the least such R+. ]]
Pages 62-63
-----------------
The spacing on the last line is bad (printer problem). Power \cap Power^{-1} lacks
space before \cap. The same in caption of Fig 4.3 and line -4 (fourth from bottom) of Page 63.
Page 63
-----------
Omitted LBA accidentally.
--begin
Coming to our specific example,
there are
{{ four }}
[[ five ]]
equivalence classes over {\em Power}$\cap$ {\em Power}$^{-1}$:
{{ $\{dfa,nfa\}$, $\{dpda\}$, $\{npda\}$, and $\{dtm,ndtm\}$. }}
[[ $\{dfa,nfa\}$, $\{dpda\}$, $\{npda\}$, $\{lba\}$, and $\{dtm,ndtm\}$. ]]
As can be seen from Figure~\ref{fig:binrel-def-equality}, they are
{{ four }}
[[ five ]]
maximal universal relations.
Given an equivalence relation $R$, the equivalence class of an element
$x\in elements(R)$ is denoted by $[x]$.
--end
Page 64
-----------
Swapped glb and lub accidentally.
--begin
As another illustration, the set of {\em all equivalence
relations over $S$} forms a
\index{Lattice!all equivalences}
{\em lattice} under the normal set inclusion operator.
The
{{ $glb$ }}
[[ $lub$ ]]
of this lattice is the {\em universal relation}
$S\times S$, and the
{{ $lub$ }}
[[ $glb$]]
of this lattice is
the {\em identity relation} $\{\langle x,x\rangle \;\mid\; x\in S\}$.
--end
Page 65
-----------
In the definition of
op : x^n elements(R) -> elements(R)
(meaning, as an n-ary cartesian product), an example would have been
handy. Something like
+ : Nat x Nat -> Nat
Page 66
-----------
Illustration 4.5.3:
{{ Also, the set $F$
with the operator $\Rightarrow$ forms a lattice, with $f_1\vee f_2$
being the least upper-bound and $f_1\wedge f_2$ being the greatest lower-bound of
two formulas
$f_1$ and $f_2$. }}
[[ Also, the set
of equivalence classes of
$F$ (each denoting a Boolean function as in Illustration 4.5.2)
with the operator $\Rightarrow$ forms a lattice, with $f_1\vee f_2$
being the least upper-bound and $f_1\wedge f_2$ being the greatest lower-bound of
two Boolean functions
$f_1$ and $f_2$. ]]
Page 71
-----------
Remove 'under a congruence' on the last line.
Page 74
-----------
The 5=5 example (second bullet) is perhaps un-necessary.
Page 76
-----------
'Question 3' and 'following exercise' are dangling.
--begin
{{ doing the following exercise. }}
[[ doing Exercise 5.4 on page 86.]]
--end
Page 86
------------
Problem 5.3, Part 5 is incorrectly paranthesized, and turns out to
be a Boolean formula that is neither true nor false. The correct
paranthesization also appears on Page 325, definition A2.
{{ ((a=>(b=>c)) => (a=>b)) => (a=>c) }}
[[ (a=>(b=>c)) => ((a=>b) => (a=>c)) ]]
Page 99
------------
The definition mu x.(if (x=0) then 0 else x+f(x-1)) has a typo.
{{ mu x.(if (x=0) then 0 else x+f(x-1)) }}
{{ mu f.(if (x=0) then 0 else x+f(x-1)) }}
This is because the least such function is of interest, since the
function f is the quantity being recursively defined.
Page 107
------------
{{ Given two strings $s_1$ and $s_2$, their concatenation, written as $s_1 s_2$,
yields a string of length $s_1 + s_2$
in the obvious way. }}
[[ Given two strings $s_1$ and $s_2$, their concatenation, written as $s_1 s_2$,
yields a string of length $length(s_1) + length(s_2)$
in the obvious way. ]]
Page 110
------------
{{ Symmetric difference:
\( (A\setminus B)\cup (B\setminus A) \) }}
[[ Symmetric difference:
\( (L_1\setminus L_2)\cup (L_2\setminus L_1) \) ]]
Page 123
------------
In Figure 8.5, FA must have a self-loop FA - 0 -> FA, and FB also must
have a self-loop FB - 1 -> FB
Page 140
------------
Caption 'Fig 9.1' is too close to the bottom of the page (Printer's mistake)
Page 153
------------
Some comments were offered to smoothen the English. Look for them
under "detailed comments" below.
Page 163
------------
In Figure 10.2, the third figure is missing moves on 0 from F_B
and A_IF.
i.e.
F_B - 0 -> BH1_BH2 and A_IF - 0 -> BH1_BH2
must be added.
Pages 177, and 178
--------------------------
The 'Figure 10.13' referred to on Page 177 is referring to the figure without
caption on Page 178.
(Caption of this figure has been chopped off- printer's mistake.)
Pages 196, Figure 11.5
--------------------------
P0 is a [0] node; P1 is !b; P2 is a [1] node
The script should have P2 defined in terms of P1 (not P0)
Page 200
------------
[14,13] is better listed as [13,14].
Page 208
------------
Illustration 12.1.2
under PR2:
under step 2.
I say "of the form 0^m 1^n" so I'm not totally wrong
But change 0^m 1^n to 0^m 1 0^n 1 if you want an exact statement.
Page 209, Section 12.1.1
------------------------
This formula has typos. Replace it with
Regular(L) =>
\exists n \in N :
\forall x,y,z in \Sigma^* :
/\ xyz \in L
/\ |y| \ge n =>
\exists u,v,w in \Sigma^* :
/\ y = uvw
/\ v <> \varepsilon
/\ \forall k >= 0:
x u v^k w z \in L
Page 215
------------
Problem 12.8 - {{ of page 12.3 }} [[ of Page 211 ]]
Page 215
------------
Problem 12.10, Part 3, no need for "is not regular"
Page 225
------------
One typo: remove the extra {b} below:
OLD:
L(S_6) = {a} L(S_6) {b} L(S_6) union
{b} L(S_6) {a} L(S_6) union
{b} L(S_6) L(S_6) union
{ epsilon }
NEW:
L(S_6) = {a} L(S_6) {b} L(S_6) union
{b} L(S_6) {a} L(S_6) union
L(S_6) L(S_6) union
{ epsilon }
Also,
It would be good to assign an exercise that asked
students to check why suggested solutions such as
the following don't work out.
L(S5) = set of strings s over a and b such that
n_a(s) - n_b(s) = constant
L(S5) = set of strings s over a and b such that
n_a(s) - n_b(s) = constant and n_a(s), n_b(s) > 0
Pages 251 and 252
-------------------------
Figure 14.3 menitoned on this page refers to the figure on Page 252 (caption truncated;
printer's mistake)
Page 259
-------------------------
Change last line from
[p,g,q_0] -> a [q,a,q_1] [q_1,g_1,q_2] ... [q_n,g_n,q_0]
to
[p,g,q_0] -> a [q,g_1,q_1] [q_1,g_2,q_2] ... [q_n,g_n,q_0]
Page 303
-------------
Caption of Figure 16.4 should change from
\caption{Mapping reduction from $A_{TM}$ to $E_{TM}$}
to
\caption{Mapping reduction from $A_{TM}$ to $\overline{E_{TM}}$}
as a mapping reduction from $A_{TM}$ to $E_{TM}$ cannot exist (if it did, then
so would one from $\overline{A_{TM}}$ to $\overline{E_{TM}}$, which would then
mean $\overline{E_{TM}}$ is not TR since
$\overline{A_{TM}}$ is not TR.
But we can build an enumerator for $\overline{E_{TM}}$, as we need to dovetail
the runs of all strings from $\Sigma^{*}$ with all possible TMs and list each TM
that halts!
Page 304
-------------
\subsubsection{Mapping reduction From $A_{TM}$ to $E_{TM}$}
should change to
\subsubsection{Mapping reduction From $A_{TM}$ to $\overline{E_{TM}}$}
for the same reasons as explained in connection with Page 303, above.
Page 320
-------------
Problem 17.4.
Change Figure~{fig:pcp-complete-example} to Figure 17.2.
Page 336
-------------
The quoted text "These are the places which cause an exponential size growth of formulas" .
A better sentence would have been "These are the places in the code causing an exponential
growth of the generated formulas."
Page 340
------------
Line -4 says "3-SAT to <>-sat". It is good to add:
[[ (Also, see Exercise 18.13.) ]]
Page 378
------------
Against "General equation format," mention that we are
illustrating only the "=" case. (The <= and >= cases
should be left as an exercise to the reader.)
Page 379
------------
Initial state rule: The initial state is always {{ q_0 }} [[ q_b ]]
In our example, the initial state is {{ 0 }} [[ 1 ]]
If the above condition holds, d = (c - a1 theta1 - ... ) div 2.
[[ Add here: Now, the equation is treated as a1x1 + a2x2 + ... + anxn = d ]]
Page 382
------------
Contrast the following guarantees: {{ where the former is likely to be offered by a }}
[[ drop this portion, stopping at the : ]]
Page 383, towards the end
------------------------------------
{{ All modern }}
[[ Virtually all modern ]]
Page 391
------------
Caption too close to bottom (printer's error)
Page 397
------------
{{ Sedgewick }}
[[ the author ]]
Page 402
------------
Could have a better caption that clearly points to the sub-figures.
Page 409
-------------
Figure is too large (scale down)
Page 439
------------
"A journey" must really begin with a paragraph offset.
Detailed comments pertaining to Page 153
-----------------------------------------------------------------
> Page 153, bottom, "Proposed RE":
>
> What's a "pair of consecutive 1s" ? The naive reader thinks of
> "consecutive 1s" as an instance of ...01...10... with some
> number n > 1 of "1s" in a row. So a "pair of consecutive 1s"
> is two such instances.
>
> But that doesn't seem to be what you intend: you seem to mean
> instead what I might call an instance of two consecutive "1s",
> i.e., an instance of ...11... .
Yes instance of consecutive 1's is what I should have said
(or instances of "11"s).
> And in requiring "at most one pair of consecutive 1s" you really
> seem to be requiring that there never be either any ...111... or
> any ...11...11... .
Precisely
>
> That I'd describe rather as requiring 'at most one instance of
> two consecutive "1s"'.
>
Agreed
> Yet your RE seems to be formulating EXACTLY ONE instance of
> two consecutive "1s"', and I think other readers will see that,
> too, and wonder at your mistake.
>
> For the sake of argument, though, let's let that quibble pass --
> maybe the readers will just accept your RE as "probably correct"
> -- and turn to the next page (p. 154), at point 2. Here you
> speak of "(i) at least two pairs of consecutive 11s" -- but surely
> you mean instead 'at least two instances of two consecutive "1s"'.
>
> Actually, your use in (ii) of the phrase "the 111 pattern" lights the
> way to much slicker reformulations than those I suggest above:
> why not speak at all times of 'a 11 pattern'? Thus on page 153:
>
> '... at most one instance of the 11 pattern ...'
>
> and on page 154:
>
> '... at least two instances of the 11 pattern ... '
Great!
>
> (and notice that the 111 pattern DOES provide a string -- indeed,
> the shortest possible string -- with two instances of the 11 pattern).
>
> Anyway, no math quibble here, just choice of words to smooth the exposition.
>
Totally agreed. These changes are bound to make this example far more useful.
> [PS: I guess you're not worried that some readers will habitually
> understand RE as "recursively enumerable" and always have to kick
> themselves to read it as "Regular Expression"? ]
That is likely but with the tool interface supporting commands such as
"retofm" and such, the word "re" is likely to acquired the desired meaning
in this context (i.e. regular expression). Fortunately,
the term 'recursively enumerable' makes an appearence only much later.
> Revised comments:
>> Yet your RE seems to be formulating EXACTLY ONE instance of
>> two consecutive "1s"',
>
> NO! but it does seem to be formulating AT LEAST one "1", which
> might even be part of a "11" (and no opportunity for any second "11"),
> which rules out the empty string and the each all-0 string.
>
>> ... and I think other readers will see that,
>> too, and wonder at your mistake.
>
> Still a valid comment, though the mistake isn't what I first thought.
I'll incorporate these observations.
> Actually, I wonder also: why write (0+ + /epsilon) and not (0*) ?
>
> And: what about the empty string? Or is that subsumed under the
> all-0 case, in your analysis (the "length-zero all-0 string")?
The all 0's machine on Page 156 -- the one that depicts all omitted strings
-- must be reworded to be "the all zeros or empty" machine.
>
>
(END OF ERRATA.)
This document was translated from LATEX by
HEVEA.