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

Contents
Abstract

## p.31 1 Regular Languages

### p.31 1.1 Finite Automata

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

#### p.35 FORMAL DEFINITION OF A FINITE AUTOMATON

p.35 DEFINITION 1.5:

DEFINITION 1.5

A finite automaton is a 5-tuple $(Q, \Sigma, \delta, q_0, F)$, where

1. $Q$ is a finite set called the states,
2. $\Sigma$ is a finite set called the alphabet,
3. $\delta: Q \times \Sigma \xrightarrow{} Q$ is the transition function,
4. $q_0 \in Q$ is the start state, and
5. $F \subseteq Q$ is the set of accept states.

#### p.44 THE REGULAR OPERATIONS

p.44 DEFINITION 1.23:

DEFINITION 1.23

Let $A$ and $B$ be languages. We define the regular operations union, concatenation, and star as follows:

• Union: $A \cup B = \lbrace x | x \in A \thickspace \text{or} \thickspace x \in B \rbrace$.
• Concatenation: $A \circ B = \lbrace xy | x \in A \thickspace \text{and} \thickspace y \in B \rbrace$.
• Star: $A^* = \lbrace x_1 x_2 \dotsb x_k | k \ge 0 \thickspace \text{and each} \thickspace x_i \in A \rbrace$.

p.45 THEOREM 1.25:

THEOREM 1.25

The class of regular languages is closed under the union operation.

### p.47 1.2 Nondeterminism

#### p.53 FORMAL DEFINITION OF A NONDETERMINISTIC FINITE AUTOMATON

For any set $Q$ we write $\mathcal{P}(Q)$ to be the collection of all subsets of $Q$. Here $\mathcal{P}(Q)$ is called the power set of $Q$.

For any alphabet $\Sigma$ we write $\Sigma_{\varepsilon}$ to be $\Sigma \cup \lbrace \varepsilon \rbrace$.

p.53 DEFINITION 1.37:

DEFINITION 1.37

A nondeterministic finite automaton is a 5-tuple $(Q, \Sigma, \delta, q_0, F)$, where

1. $Q$ is a finite set of states,
2. $\Sigma$ is a finite alphabet,
3. $\delta: Q \times \Sigma_{\varepsilon} \xrightarrow{} \mathcal{P}(Q)$ is the transition function,
4. $q_0 \in Q$ is the start state, and
5. $F \subseteq Q$ is the set of accept states.

#### p.54 EQUIVALENCE OF NFAS AND DFAS

pp.56- EXAMPLE 1.41、FIGURE 1.42、FIGURE 1.43 を見ると直感が得られる。 $\mathcal{P}(Q)$ を $\delta$ で繋いでやったDFAはNFAの文法と等価になる。 $q_0 \xrightarrow{a} q_1 \xrightarrow{\varepsilon} q_2$ は、 「$q_1$ または $q_2$ に遷移する」と考えることができるので、 $q_0 \xrightarrow{a} \lbrace q_1, q_2 \rbrace$ に置き換える。

#### p.58 CLOSURE UNDER THE REGULAR OPERATIONS

p.60 THEOREM 1.47:

THEOREM 1.47

The class of regular languages is closed under the concatenation operations.

• $\text{language 1} = \lbrace \text{“hell”}, \text{“hello”} \rbrace$
• $\text{language 2} = \lbrace \text{“world”}, \text{“old”} \rbrace$
• $(\text{language 1}) \circ (\text{language 2}) = \lbrace \text{“hellworld”}, \text{“hellold”}, \text{“helloworld”}, \text{“helloold”} \rbrace$

において、input “hell” の時点でlanguage 1のaccept stateだが、language 2に遷移したbranchが正解とは限らない。 最終的なstringが “helloold” だった場合は “hello+old” というconcatenationなので、 language 1では $(\text{input: “hell”}) \text{language 1 accept state} \xrightarrow{\text{“o”}} (\text{input: “hello”}) \text{language 1 accept state} \xrightarrow{\varepsilon} (\text{input: “hello”}) \text{language 2 start state}$ という遷移を選択することになる。

### p.63 1.3 Regular Expressions

#### p.64 FORMAL DEFINITION OF A REGULAR EXPRESSION

p.64 DEFINITION 1.52:

DEFINITION 1.52

Say that $R$ is a regular expression if $R$ is

1. $a$ for some $a$ in the alphabet $\Sigma$,
2. $\varepsilon$,
3. $\emptyset$,
4. $(R_1 \cup R_2)$, where $R_1$ and $R_2$ are regular expressions,
5. $(R_1 \circ R_2)$, where $R_1$ and $R_2$ are regular expressions, or
6. $(R_1^*)$, where $R_1$ is a regular expression.

In items 1 and 2, the regular expressions $a$ and $\varepsilon$ represent the languages $\lbrace a \rbrace$ and $\lbrace \varepsilon \rbrace$, respectively. In item 3, the regular expression $\emptyset$ represents the empty language. In item 4, 5, and 6, the expressions represent the languages obtained by taking the union or concatenation of the languages $R_1$ and $R_2$, or the star of the language $R_1$, respectively.

2. は空文字列 "” とマッチするが、3. は何にもマッチしない。

For convenience, we let $R^+$ be shorthand for $RR^*$ . … So $R^+ \cup \varepsilon = R^*$. In addition, we let $R^k$ be shorthand for the concatenation of $k R$'s with each other.

When we want to distinguish between a regular expression $R$ and the language that it describes, we write $L(R)$ to be the language of $R$.

#### p.66 EQUIVALENCE WITH FINITE AUTOMATA

p.69 LEMMA 1.60:

LEMMA 1.60

If a language is regular, then it is described by a regular expression.

FIGURE 1.67、FIGURE 1.69 を見ると理解しやすい。 DFAに状態 $q_{\text{start}}, q_{\text{accept}}$ を加えて generalized nondeterministic finite automaton (GNFA) に変換し、このGNFAの状態を1つづつ減らして2状態のGNFAにする。 GNFAはtransition functionに正規表現を書けるNFAで、ここでは以下の条件を満たすようにする (special form)。

1. $q_{\text{start}}$ からは他の全てのstateに矢印が伸びるが、$q_{\text{start}}$ への矢印は無い。
2. $q_{\text{accept}}$ は唯一のaccept stateで、他の全てのstateからは $q_{\text{accept}}$ への矢印が存在するが、$q_{\text{accept}}$ からの矢印は無い。
3. $q_{\text{start,accept}}$ 以外のstateは、他の全state への/からの 矢印がある

p.72:

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

### p.77 1.4 Nonregular Languages

#### p.77 THE PUMPING LEMMA FOR REGULAR LANGUAGES

Pumping lemma If $A$ is a regular language, then there is a number $p$ (the pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:

1. for each $i \ge 0$, $xy^iz \in A$,
2. $|y| > 0$, and
3. $|xy| \le p$.

この $p$ を $4$ と仮定する（適当）。 長さが4以上で $R$ を満たす文字列を羅列する[*]。

• $\texttt{0000}$
• $\texttt{1000}$
• $\texttt{00000}$
• $\texttt{10000}$

$\texttt{0000}$ を3つの文字列に分割する。1つ目と3つ目は空文字列 $\varepsilon$ でも良いが、2つ目は長さ1以上にする。 例えば $\texttt{0} ~ \texttt{0} ~ \texttt{00}$ と分割する。このとき、

• 2つ目の文字列 ($\texttt{0}$) が無い場合: $\texttt{0} ~ \texttt{00}$
• 2つ目の文字列 ($\texttt{0}$) が2つある場合: $\texttt{0} ~ \texttt{0} ~ \texttt{0} ~ \texttt{00}$
• 2つ目の文字列 ($\texttt{0}$) が3つある場合: $\texttt{0} ~ \texttt{0} ~ \texttt{0} ~ \texttt{0} ~ \texttt{00}$

の文字列も全て $R$ を満たす。よってこの分割はpumping lemmaの条件を満たす。

1文字・1文字・残り というふうに[*]を分割してみると、これらは全てpumping lemmaの条件を満たすことが分かる。 2つ目の1文字は常に $0$ で、これは無くても・あっても・繰り返しても (pumping) $R$ を満たすため。

• $\texttt{0} ~ \texttt{0} ~ \texttt{00}$
• $\texttt{1} ~ \texttt{0} ~ \texttt{00}$
• $\texttt{0} ~ \texttt{0} ~ \texttt{000}$
• $\texttt{1} ~ \texttt{0} ~ \texttt{000}$

$R$ はpumping length $p=5$ 以上を持つことも自明だ。 それよりも、最小のpumping lengthを探す方が感心があるだろう。 $p=3$ はどうか。長さが3の $R$ を満たす文字列は以下の2つで、両方ともpumping lemmaを満たす分割が見つかる。

• $\texttt{000}$ → $\texttt{0} ~ \texttt{0} ~ \texttt{0}$
• $\texttt{100}$ → $\texttt{1} ~ \texttt{0} ~ \texttt{0}$

よって $R$ はpumping length $p=3$ を持つ。 $p=2$ も同様で、$R$ はpumping length $p=2$ を持つ。

• $\texttt{00}$ → $\texttt{0} ~ \texttt{0} ~ \varepsilon$
• $\texttt{10}$ → $\texttt{1} ~ \texttt{0} ~ \varepsilon$

$p=1$ は満たさない。pumping lemmaを満たす分割ができないため。

• $\texttt{0}$ → $\varepsilon ~ \texttt{0} ~ \varepsilon$ ($\texttt{0}$ を消すと $R$ を満たさない)
• $\texttt{1}$ → $\varepsilon ~ \texttt{1} ~ \varepsilon$ ($\texttt{1}$ を消すと/が2つ以上あると $R$ を満たさない)

（この場合ループ部分の解釈が描き表せない…？ $p$ が状態数より小さい場合は、鳩の巣原理による解釈の範囲外だから？）

ちょっと書き疲れたので雑に書くと、$p=2$ だが長さ2の文字列は無い。 しかしpumping lemmaは満たしている。 スター ($^*$) が1つも無い正規表現はこのようなtrivialで面白いことが言える。

ところで(2)鳩の巣原理はpigeonhole principleと言うのか。かわいい(?)。 鳩の巣原理が登場する証明は常にスマートで感動する。

p.80 EXAMPLE 1.74 で登場するintersection $\cap$ は p.4 で登場していて、 $A=\lbrace \texttt{good}, \texttt{bad} \rbrace, B=\lbrace \texttt{good}, \texttt{girl} \rbrace$ ならば、$A \cap B = \lbrace \texttt{good} \rbrace$ ということ。

## p.101 2 Context-Free Languages

### p.102 2.1 Context-Free Grammars

#### p.104 FORMAL DEFINITION OF A CONTEXT-FREE GRAMMAR

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$. Say that $u$ derives $v$, written $u ⇒ v$, if $u = v$ or if a sequence $u_1, u_2, …, u_k$ exists for $k ≥ 0$ and …

### p.106 Designing context-free grammars

p.107

WIP

Second, constructing a CFG for a language that happens to be regular is easy if you can first construct a DFA for that language.

また例が無くて少し難しかった。1つ例を考えてみた。

$\texttt{0(01)*1} (\texttt{})$ 01 0011 001011 00101011

• start: R0

• R0 -> 0 R1

• R1 -> 0 R2 | 1 RF

• R2 -> 1 R1

• RF -> eps

• start: R0

• R0 -> 0 R1

• R1 -> 0 R2 | 1

• R2 -> 1 R1