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:
DEFINITION 1.64
A generalized nondeterministic finite automaton is a 5-tuple, $(Q, \Sigma, \delta, q_{\text{start}}, q_{\text{accept}})$, where
- $Q$ is the finite set of states,
- $\Sigma$ is the input alphabet,
- $\delta: (Q - \lbrace q_{\text{accept}} \rbrace) \times (Q - \lbrace q_{\text{start}} \rbrace) \xrightarrow{} \mathcal{R}$ is the transition function,
- $q_{\text{start}}$ is the start state, and
- $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で追加された節。