Contents

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

p.29 Part One: Automata and Languages

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.

証明:2つの有限オートマトン (DFA) の状態の直積を状態を持つDFAを考え、 2つのDFAを同時進行するように考える。 p.59 では $q \xrightarrow{\varepsilon} \lbrace q1, q2 \rbrace$ と2つのDFAを同時進行するようなNFAを使ってもっと簡単に証明している…すごい。

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$.

例えば $Q = \lbrace q_0, q_1, q_2 \rbrace$ なら $\mathcal{P}(Q) = \lbrace \emptyset, \lbrace q_0 \rbrace, \lbrace q_1 \rbrace, \lbrace q_2 \rbrace, \lbrace q_0, q_1 \rbrace, \lbrace q_1, q_2 \rbrace, \lbrace q_2, q_0 \rbrace, \lbrace q_0, q_1, q_2 \rbrace \rbrace$。

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.

複数のDFAを取り込むようなNFAを構成すれば、DFA1のaccept statesのnext state ($\xrightarrow{\varepsilon}$) をDFA2のstart stateにできるのか。すごいアイデアだ。 DFA1のaccept statesに到達したらただちにDFA2のstart stateに遷移するとは限らない点に注意。 例えば

  • $\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

一部のプログラミング言語の正規表現と “呼ばれるもの” で見られる先読み・後読み (looking-forward/backward) って正規言語なのかな。そうでは無い気がする。 1.4で登場するpumping lemmaで証明できそうだ。そのうちやってみよう。

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$.

日本語ではポンピング定理・反復補題と呼ぶらしい。

例 1: p.63 正規表現 $R = (\texttt{0}\cup\texttt{1})\texttt{0}^*$ は正規言語であるので、pumping lemmaを満たすpumping length $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の条件を満たす。

逆に $\varepsilon ~ \texttt{0000} ~ \varepsilon$ という分割はpumping lemmaの条件を満たさない。 2つ目の文字列 $\texttt{0000}$ が無い場合: $\varepsilon$ は $R$ を満たさないからだ。

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}$

長さが4以上の $R$ の全ての文字列に対してこのような3分割が見つかったため、$R$ はpumping length $p=4$ を持つ。 $R$ は正規言語であるため必ずpumping lengthが存在する。

$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$ を満たさない)

従って、$R$ の最小のpumping lengthは $p=2$ である。

実は $R$ がpumping lengthは $p=2$ を持つことは当然で、下図のようにDFAの状態数が2だからである。 その証明は p.79 PROOF にある。

/ja/computation/2021-12-25-23-48-54.png
DFA of $R = (\texttt{0}\cup\texttt{1})\texttt{0}^*$

私の直感を描いた図を貼っておく。

/ja/computation/2021-12-25-17-39-39.png
$R = (\texttt{0}\cup\texttt{1})\texttt{0}^*$

例 2: p.68 $R = (\texttt{ab}\cup\texttt{a})^*$

/ja/computation/2020-09-21-16-07-01.png
$R = (\texttt{ab}\cup\texttt{a})^*$

図のようにpumpingのループ部分は複数の解釈ができる。

状態数は2なので $p \le 2$ 。こちらはなんと、$p=1$ である。 長さが1で $\in R$ な文字列は $\texttt{a}$ のみで、 $\varepsilon ~ \texttt{a} ~ \varepsilon$ と分割できるからだ。

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

例 3: $R = \texttt{a}$

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

関連して、もしpumping lemmaの逆(pumping lengthが存在する言語は正規言語である) が成り立つのだろうか? 成り立たないと思われる。 つまり、「pumping lengthは存在するが正規ではない」言語が存在すると考える。 pumping lemmaの逆が成り立つならば、 「長さに上限のある言語は正規言語である」という定理が成立する。 pumping lengthをこの上限より大きく取ればpumping lemmaがtrivialに (本書の言葉を借りるとvacuouslyに)成り立つからだ。 例えば「50字以内、alphabet $\texttt{[a-z]}$ の回文は正規言語である」 と言えてしまう。…うーんこれに関しては正規言語である気もする。もっと良い例が無いだろうか…

ところで(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

p.163 Part Two: Computability Theory

p.165 3 The Church-Turing Thesis

p.193 4 Decidability

p.215 5 Reducibility

p.255 6 Advanced Topics in Computability Theory

p.273 Part Three: Complexity Theory

p.275 7 TimeComplexity

p.331 8 Space Complexity

p.363 9 Intractability

p.393 10 Advanced Topics in Complexity Theory