オートマトン 基礎からざっくり

情報科でオートマトンの講義を履修しているので思考整理と備忘録を含めたメモ．
ものごとの定義や数学的厳密性等々は皆無でなんとなく理解するということを念頭においたものなのであしからず．

<font color="red">**2021.01.03補足1　未完成記事です！徐々にここに追記します！**</font>
<font color="red">**2021.01.03補足2　引用まだちゃんと記載しておりません！**</font>

【この記事で分かること】
・有限オートマトンにまつわる単語のざっくりとした概念
・有限オートマトンについて書かれた書籍のざっくりとした流れ
・<font color="deepskyblue">有限オートマトンにまつわる基本的な変換問題の解法</font>
・有限オートマトンにまつわる正規表現

【この記事で触れないこと】
・有限オートマトンじゃないオートマトンたち
・有限オートマトンにまつわる単語の厳密な定義
・有限オートマトンの数学的厳密性
・有限オートマトンの工学的応用例
・有限オートマトンにまつわる基本的な変換問題の解法の理由や必然性
・<font color="red">バリデーション的な実装面で汎用性のある正規表現</font>
・集合論，写像論，グラフ理論
・DFAとNFAの概念的な違い，NFAとε-NFAの概念的な違い
・形式言語関連

【知っていてほしいこと】
・状態遷移図の読み方　(図を載せるのが面倒なので......申し訳ないです)
・「集合」の基礎の基礎の基礎

#オートマトン / 有限オートマトン とは
オートマトンとは一言で表すと「形式言語を識別するマシン」．ある文字列が設定した条件と一致するか否かの判定を行う．
その中でも，計算機がある入力に対して **受理** or **拒否** するか表すモデルを「**<font color="red">有限Automaton**</font>」と呼ぶ．
有限Automatonは「<font color="red">**状態遷移図**</font>」という図によって表現する

#有限オートマトンについて詳しく
###有限オートマトンは「5つの組」によって定義される
1. **状態 <font color="red">Q</font>**；すごろくでいうところのマスにあたる
2. **入力 <font color="red">Σ</font>**；すごろくでいうところのサイコロにあたる
3. **遷移関数 <font color="red">δ</font>**；すごろくでいうところの現在のマスからサイコロのある出目がでたときの移動先マス
4. **開始状態 <font color="red">q0</font>**；すごろくでいうところのスタートマス
5. **受理状態 <font color="red">F</font>**；すごろくでいうところのゴールマス (複数存在することもある)

[注意]　厳密にいうと集合だったりする

###決定性について
ある有限Automatonの次の状態 (すなわち遷移関数δで定まる値) が一意である，すなわち次の状態がいつでも1種類だけの一方通行であるとき，この有限Automatonは「**<font color="red">決定性</font>がある**」という．

ちょっと厳密な決定性とは
**【Q☓Σによる遷移先が一意であること】**である
これを言い換えると
1. **遷移先が~~2つ以上~~**ある (分岐する) ものは<font color="red">ダメ</font>
2. **遷移先が~~0こ~~**である (定義されていない) ものは<font color="red">ダメ</font>
この両方に引っかからないものが「決定性がある」ということである．

[補足] <font color="red">**ε**</font> で表される **文字入力なしの遷移** も「決定性なし」に分類される (らしい)


#DFAとNFAについて

上記の決定性に関して，「**決定性がある**」有限Automatonのことを
　<font color="red">**決定性有限Automaton**</font>
あるいは，その英語表記 "**D**eterminate **F**inte **A**utomaton" の頭文字から
　<font color="red">**DFA**</font>
と呼ぶ．(つまりDFAは **対1** の関係がある)

それに対して，「**決定性がない**」有限オートマトンのことを
　<font color="red">**非決定性有限Automaton**</font>
あるいは，その英語表記 "**N**on-determinate **F**inte **A**utomaton" の頭文字から
　<font color="red">**NFA**</font>
と呼ぶ．(つまりNFAは **対多** の関係がある)

DFAとNFAの数学的な違いとしては，遷移関数δ の定義が
DFA：【Q☓Σ から **Q** への遷移関数】
NFA：【Q☓Σ から **2^Q** への遷移関数】
という差異がある．
[注意] Q☓Σ はあくまで集合の演算である

#正規表現について
言語の中にどのような語が含まれているのか表している「集合」をわかりやすく**式に近い形**で表すひとつの方法に「<font color="red">**正規表現**</font>」がある．

正規表現はざっくり**3+1個の演算記号**と**少しのルール**で表される．

###演算記号
1. **積** <font color="red">**・**</font>；書いてあるものと一致 ```例 aab -> {aab}```
2. **和** <font color="red">**+**</font>；「または」どちらか一方の選択 ```例 aab+aa -> {aab, aa}```
3. **閉包** <font color="red">**＊**</font>；0(ε) 以上ぜんぶ ```例 a* -> {ε, a, aa, aaa, ... }```

+α. <font color="red">**(**</font> **カッコ** <font color="red">**)**</font>；まとまりを作る ```例 (0+1)＊```

[補足] 積を「**連接**」，閉包を「**スター演算**」とも呼ぶ．
[注意] 積は dot product であり cross product を使うと誤り．また dot product の省略可能． (基本的に省略しているイメージ)

###ルール
・ 上の記号を用いて1つの式として表す
・ **空集合φ** と **ε** も正規表現のうちのひとつ
・ 式変形について，積が非可換であること以外はだいたいいつもと同じ

#線形再起方程式 (線形回帰方程式)
正規表現は下記のような性質を持つ

```math
x = s + xt\quad\Longrightarrow\quad x = st*\\
x = s + tx\quad\Longrightarrow\quad x = t*s
```


これ (どれ？) を「<font color="red">**線形再起(回帰)方程式**</font>」と呼ぶ．

DFAに関してこれを用いて受理状態について求めたものが正規表現であるため，**DFAから正規表現の変換を可能にする**性質である

###DFAから正規表現を求める
<font color="deepskyblue">**step0.**</font>
　DFAの状態遷移図が与えられる
<font color="deepskyblue">**step1.**</font>
　各状態毎に ```(遷移先の状態) = (元の状態A)[入力値a] + (元の状態B)[入力値b] + ...``` という線形的な方程式をすべての状態について立式する．
<font color="deepskyblue">**step2.**</font>
　和の部分に関して**線形回帰方程式**を用いることで積へと変換する．このとき基本的に ```x``` にあたるものは q0 のような状態．
<font color="deepskyblue">**step3.**</font>
　状態を代入できるものは代入し，方程式を解く
<font color="deepskyblue">**step4.**</font>
　最終的に
　　```[受理状態] = (正規表現)```
　となれば完了．

[注意] 式変型の順番により，正解が複数通り存在することもある．

#やっと本題 ： オートマトンで求めるもの
上で **DFA -> 正規表現** という変換を行ったが，逆は簡単に求めることはできない．オートマトンで重要なのはこの逆を求めること，すなわち **正規表現 -> DFA** を求めることである．

###正規表現からDFAを求める流れ
<font color="blue">**[正規表現]**</font>
=( 帰納的構成法 )=> **[ε-NFA]**
=( ε-動作の除去 )=> **[NFA]**
=( サブセット構成法 )=> **[冗長的なDFA]**
=( 最小化 )=> <font color="blue">**[DFA]**</font>

[補足] 世の中のオートマトンに関する書籍は，サブセット構成法，ε動作の除去，帰納的構成法，最小化の順に書かれていることが多いと思った．(定義的にはその方がわかりやすいしね)

#NFAからDFA 〜サブセット構成法〜
後日記載

#ε-NFAからNFA 〜ε-動作の除去〜　およびε-NFAについて
後日記載


#正規表現からε-NFA 〜帰納的構成法〜
後日記載

#DFAの最小化
後日記載

#まとめ : 正規表現から最小化されたDFAまで
後日記載