ryamadaのコンピュータ・数学メモ

遺伝学・遺伝統計学関連の姉妹ブログ『ryamadaの遺伝学・遺伝統計学メモ』
京都大学大学院医学研究科ゲノム医学センター統計遺伝学分野のWiki
講義・スライド
医学生物学と数学とプログラミングの三重学習を狙う学習ツール
駆け足で読む○○シリーズ
ぱらぱらめくるシリーズ
カシオの計算機
オンライン整数列大辞典

駆け足で読む『計算理論の基礎』第１巻：オートマトンと言語

駆け足で読むシリーズ計算理論オートマトン有限オートマトン形式言語文脈自由文法正規表現複雑さ

1 正規言語
- 「計算機とは何か？」を理解するために計算をモデル化する
- 計算機設計的な位置づけで「有限オートマトン」があり、文字列を読み取るという立場から正規表現がある
- 1.1 有限オートマトン
  - 有限オートマトンの定義
    - ５個組で決まる
      - $Q$ は状態の有限集合
      - $\Sigma$ はアルファベットと呼ばれる有限集合
      - $\delta:Q\times \Sigma \to Q$ は遷移関数
      - $q_0 \in Q$ は開始状態
      - $F \subset Q$ は最終状態の集合
  - 有限オートマトンが受理(認識する)する(最終状態として作る)文字列のすべての集合を、そのオートマトンの言語と言う
  - ある有限オートマトンで認識される言語を正規言語(regular language)という
  - 有限オートマトンの状態推移に確率的要素を加味するとマルコフ連鎖
  - 有限オートマトンとその言語の性質は、言語に成り立っている演算の性質として考えることができる
    - ２つの言語の和集合、２つの言語の積集合、１つの言語のアルファベットの列集合
  - 言語が定義する文字列かどうかを判定できること、ルールに従って判定できること、集合の内包表現の判定ができること、を目指しており、有限オートマトンはそのようなルールであり、それの機械上の実装が有限オートマトンを用いた計算機設計である
- 1.2 非決定性
  - 既述の有限オートマトンでは文字列の並びに関して、想定するべき状態は１であった
  - 一つの文字列に対して想定するべき状態が複数になる可能性を許すと、その可能性(のすべて)を想定しながら読み進む必要がある
  - 並列処理に相当するとも言えるし、状態が分岐木になっているとも言える
  - 非決定性有限オートマトンの定義
    - ５個組で決まる
      - $Q$ は状態の有限集合
      - $\Sigma$ はアルファベットと呼ばれる有限集合
      - $\delta:Q\times \Sigma_{\epsilon} \to P(Q)$ は遷移関数
      - $q_0 \in Q$ は開始状態
      - $F \subset Q$ は最終状態の集合
    - 前掲の有限オートマトンの定義から $\delta$ が変化した
    - $\Sigma_{\epsilon}=\{\Sigma,\epsilon\}$ とし、ここで $\epsilon$ は状態推移に関して「複数の可能性があるので、保留にしておく」意味合いである
    - $P(Q)$ は集合 $Q$ のべき集合
  - 決定性有限オートマトンと非決定性有限オートマトンとは同じクラスの言語を認識する。このことを、決定性有限オートマトンと非決定性有限オートマトンが等価であると言う
- 1.3 正規表現
  - 正規表現の正式な定義(帰納的定義になっている)
    - Rが正規表現であるとは、次のいずれかであること
      - 1. $\Sigma$ に属する $a$ : $\{a\}$
      - 2. 空列 $\epsilon$ : $\{\epsilon \}$
      - 3. 文字列を含まない言語: $\phi = \{\;\}$
      - 4. $R_1,R_2$ が正規表現であるとして、その和集合
      - 5. $R_1,R_2$ が正規表現であるとして、その積集合
      - 6. $R_1$ が正規表現であるとして、その任意回積集合
  - 正規表現と有限オートマトンとは、その記述能力において等価
- 1.4 非正規言語
  - ある言語が正規でないことを証明すること
2 文脈自由言語
- 有限オートマトン〜正規表現では記述できない言語としての文脈自由言語
- ヒトの言語の記述から発生
- 再帰構造がある(名詞句と動詞句、名詞句内の動詞句、動詞句内の名詞句)
- プログラミング言語の仕様記述・コンパイラ作成
- 構文解析部(パーサー)
- プッシュダウン・オートマトンが文脈自由言語に対応する
- 2.1 文脈自由文法
  - 文脈自由文法の定義
    - ４個組で決まる
      - $V$ は変数と呼ばれる有限集合
      - $\Sigma$ は終端記号と呼ばれる $V$ と共通部分をもたない有限集合
      - $R$ は左辺が変数、右辺が変数と終端記号からなる文字列であるような変換規則の有限集合
      - $S$ は開始変数
  - 正規表現との違いは、推移関数でなく、変換規則と書かれている。後述のようにこの違いは、「スタック」を取り入れることに切り替えられる
- 2.2 プッシュダウン・オートマトン
  - スタックと呼ばれる、情報を保持しておく装置が必要で、その保持した情報を取り出したり、保持領域に格納したりする作業が必要
  - プッシュダウンオートマトンの定義
    - ５個組で決まる
      - $Q$ は状態の集合
      - $\Sigma$ は入力アルファベットと呼ばれる集合
      - $\Gamma$ はスタック・アルファベット
      - $\delta:Q\times \Sigma_{\epsilon} \times \Gamma_{\epsilon} \to P(Q\ \Gamma_{\epsilon}$ は遷移関数
      - $q_0 \in Q$ は開始状態
      - $F \subset Q$ は最終状態の集合
- 2.3 非文脈自由言語