Introduction to the Theory of Computation, 3rd by Michael Sipser 読書メモ


Introduction to the Theory of Computation, 3rd by Michael Sipser (邦訳:計算理論の基礎) の読書メモ


The symbol $\mathcal{R}$ is the collection of all regular expressions over the alphabet $\Sigma$

p.73 DEFINITION 1.64:


A generalized nondeterministic finite automaton is a 5-tuple, $(Q, \Sigma, \delta, q_{\text{start}}, q_{\text{accept}})$, where

  1. $Q$ is the finite set of states,
  2. $\Sigma$ is the input alphabet,
  3. $\delta: (Q - \lbrace q_{\text{accept}} \rbrace) \times (Q - \lbrace q_{\text{start}} \rbrace) \xrightarrow{} \mathcal{R}$ is the transition function,
  4. $q_{\text{start}}$ is the start state, and
  5. $q_{\text{accept}}$ is the accept state.

3. は $\delta: (Q - \lbrace q_{\text{start}} \rbrace) \times \mathcal{R} \xrightarrow{} (Q - \lbrace q_{\text{accept}} \rbrace)$ ではない。 この式の矢印とGNFAの矢印は別物。 3. の式はtransition function (mapping) のdomain、range(p.7 FUNCTIONS AND RELATIONS 参照)を定めているだけ。

Part One: Automata and Languages (p.29)

1 Regular Languages (p.31)

1.1 Finite Automata (p.31)

そういえば重量センサーの自動ドアって子供のときどっかにあったな… 昭和まで主流だったらしい。

1.2 Nondeterminism (p.47)

1.3 Regular Expressions (p.63)

1.4 Nonregular Languages (p.77)

2 Context-Free Languages (p.101)

2.1 Context-Free Grammars (p.102)

Formal definition of a context-free grammar (p.104)

If $u$, $v$, and $w$ are strings of variables and terminals, and $A \xrightarrow{} w$ is a rule of the grammar, we say that $uAv$ yields $uwv$, written $uAv ⇒ uwv$.

$\xrightarrow{}$ は文法のルール、$⇒$ はルールの適用。

2.2 Pushdown Automata (p.111)

Equivalence with context-free grammars (p.117)

2.4 Deterministic Context-Free Languages (p.130)

決定性文脈自由言語。3rd editionで追加された節。

Part Two: Computability Theory (p.163)

3 The Church-Turing Thesis (p.165)

4 Decidability (p.193)

5 Reducibility (p.215)

6 Advanced Topics in Computability Theory (p.255)

Part Three: Complexity Theory (p.273)

7 TimeComplexity (p.275)

8 Space Complexity (p.331)

9 Intractability (p.363)

10 Advanced Topics in Complexity Theory (p.393)