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

Contents
Abstract

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

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 参照）を定めているだけ。

## 1 Regular Languages (p.31)

### 1.1 Finite Automata (p.31)

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

## 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{}$ は文法のルール、$⇒$ はルールの適用。