# オートマトンと数理言語論

## 概要
計算可能性とかのお話をやります
毎授業の最初に小テスト、OCW-iに提出

## 第1回
今回は数学的内容がメイン
### 集合について
大体やったので省略！ｗ
7枚目のスライドは$x \equiv_i x$ではなく$i \equiv_i i$

### グラフについて
頂点と辺の集合で構成される
無向グラフと有向グラフの2種類、両者の違いは点から点への辺の向きを考えるかどうか
任意の2頂点間に辺がある場合、完全グラフと呼ぶ
パス:辺をたどってできた頂点の列、特に同じ点を複数回通らないパスを単純パスと呼ぶ
グラフ内の任意の接点対の間にパスが存在すれば、それは連結であるという
始点と終点のみが同一でサイクル状のものを単純巡回と呼ぶ(始点→別の点→終点みたいなのは単純巡回ではない)
単純巡回を含まない連結なグラフを木と呼ぶ
有向グラフの場合、次数を入次数と出次数とで分ける必要がある

### 文字列と言語について
文字列を定義する空でない有限集合をアルファベットと呼び、アルファベットの要素を文字と呼ぶ
文字を有限個並べれば文字列となり、文字列$w$の長さは$|w|$で定義される
文字列の長さが$0$の場合、長さは$\varepsilon$とする
辞書式順序:短い方が先に来る、同一の長さの物同士は辞書式で並び替え

### 論理について

Boole : 人名
Boole 代数
Boolean : Boole の形容詞形
Bool : Boolean の省略
:x: Bool 代数

略

### 定理と証明について
あとで書くかもしれない

---
### 演習問題(p.30~31)
#### 4
$a \times b$個
#### 5
$2^c$個
#### 7
(1)
(2)2実数に対する順序関係$\leqq$
(3)2直線に対する関係$\perp$

---

## 第2回
### 有限オートマトン
メモリ容量が有限に制限された計算モデルのこと
例:自動ドア
フロントパッドとリアパッドにそれぞれ人がいるかどうかでドアの開閉を設定する
フロントとリアに人がいるかどうかのパターンは有限個
有限オートマトンは一般に状態遷移図を書いて表現することが多い

> **定義1.5**
> 有限オートマトンは5個組$(Q, \sum, \sigma, q_0, F)$で与えられる。

ここで、
- $Q$ : 状態と呼ばれる有限集合$\{q_1, q_2, q_3, \ldots\}$
- $\sum$ : アルファベットと呼ばれる有限集合
- $\sigma$ : 遷移関数。$\sigma :Q \times \sum \rightarrow Q$
- $q_0$ : 開始状態。状態 $Q$ の中のどれか1個
- $F$ : 受理状態の集合。

具体例は配布資料にいっぱいあるのでそれを参照してね
例1.15は状態遷移図が書けないので注意

### 計算の定義
有限オートマトンを$M =(Q, \sum, \sigma, q_0, F)$、文字列を$w=w_1w_2w_3\ldots w_n$とする。機械$M$が文字列$w$を受理するとは、以下の3条件を満たす状態の列$r_0,r_1, \ldots r_n \in Q$が存在することをいう。

- $r_0 = q_0$
- $\sigma(r_i, w_i) = w_{i+1}$
- $r_n \in F$

> **定義1.16**
> 有限オートマトンで認識される言語を正規言語という。

### 有限オートマトン設計
1. 状態を書き出して割り当てる(ゴールの見通しをよくするといいかもしれない)
2. 状態遷移を矢印で書き加えていく
3. 開始/受理状態を設定する

---
### 演習問題

digraph a {
	a
	b
	c
	d[shape = doublecircle]
	a->b[label="0"]
	a->c[label="1"]
	c->d[label="0"]
	d->c[label="1"]
	d->d[label="0"]
	c->c[label="1"]
}

digraph a {
	a
	b
	c
	d[shape = doublecircle]
	a->b[label="1"]
	b->c[label="1"]
	c->d[label="1"]
	a->a[label="0"]
	b->b[label="0"]
	c->c[label="0"]
    d->d[label="0,1"]
}

---

## 第3回
### 決定性オートマトンと非決定性オートマトン
- 決定性オートマトン(DFA):全ての状態において、遷移先が一意に定まるようなものを指す。各遷移はアルファベット上の文字が対応する。
- 非決定性オートマトン(NFA):状態によっては、遷移先が複数存在したりあるいは遷移先が存在しない場合があるようなものを指す。各遷移にはアルファベットに加えて「空列$\varepsilon$」が許される。

NFAで実装した方が遷移図がすっきりすることがある(資料の例1.30参照)

### NFAの厳密な定義
非決定性有限オートマトンNFAは以下の$5$個組で与えられる。
- $Q$:状態と呼ばれる有限集合
- $\sum$:アルファベットと呼ばれる有限集合
- $\delta$:遷移関数。ただし$\delta: Q \times \sum_{\varepsilon} \rightarrow 2^Q$
- $q_0$:開始状態。状態$Q$のどれか一つ。
- $F$:受理状態の集合。$F \subset Q$

ただし、$\sum_{\varepsilon} = \sum \cup \{\varepsilon\}$
DFAとの大きな違いは遷移関数。DFAの場合$\sigma :Q \times \sum \rightarrow Q$であった。

### NFAとDFAの等価性
機械$M_1$と$M_2$が等価文字列$\Leftrightarrow$ $L(M_1) = L(M_2)$
結果が同じであれば2つの機械は等価文字列である。
> **定理1.39**
> 全てのNFAに対し等価なDFAが存在する。

## 第8回
撮り忘れあります

## 第9回

## 第10回

## 第11回

## 第12回
何枚かスクショ抜けてます

## 第13回

## コメント
忘れてなければあとで演習の答えのスクショ貼る
↑OCW-iに解答上がってるので貼りません、解散
オー:tomato:ン
第8回以降は録画，授業資料配布一切ないのでスクショをここに貼っていく予定です
第6回までの内容はまとめるかもしれないしまとめるかもしれないです，だれかまとめてくれるととても助かる