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

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

2021.01.03補足1　未完成記事です！徐々にここに追記します！
2021.01.03補足2　引用まだちゃんと記載しておりません！

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

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

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

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

#有限オートマトンについて詳しく
###有限オートマトンは「5つの組」によって定義される

1. 状態 Q；すごろくでいうところのマスにあたる
2. 入力 Σ；すごろくでいうところのサイコロにあたる
3. 遷移関数 δ；すごろくでいうところの現在のマスからサイコロのある出目がでたときの移動先マス
4. 開始状態 q0；すごろくでいうところのスタートマス
5. 受理状態 F；すごろくでいうところのゴールマス (複数存在することもある)

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

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

ちょっと厳密な決定性とは
**【Q☓Σによる遷移先が一意であること】**である
これを言い換えると

1. 遷移先が2つ以上ある (分岐する) ものはダメ
2. 遷移先が0こである (定義されていない) ものはダメ
   この両方に引っかからないものが「決定性がある」ということである．

[補足] ε で表される 文字入力なしの遷移 も「決定性なし」に分類される (らしい)

#DFAとNFAについて

上記の決定性に関して，「決定性がある」有限Automatonのことを
　決定性有限Automaton
あるいは，その英語表記 "Determinate Finte Automaton" の頭文字から
　DFA
と呼ぶ．(つまりDFAは 対1 の関係がある)

それに対して，「決定性がない」有限オートマトンのことを
　非決定性有限Automaton
あるいは，その英語表記 "Non-determinate Finte Automaton" の頭文字から
　NFA
と呼ぶ．(つまりNFAは 対多 の関係がある)

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

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

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

###演算記号

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

+α. ( カッコ )；まとまりを作る 例 (0+1)＊

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

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

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

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

これ (どれ？) を「線形再起(回帰)方程式」と呼ぶ．

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

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

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

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

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

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

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

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

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

#DFAの最小化
後日記載

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