第1回

オートマトンを学ぶ意味

• エレベータの設計ができる!!
• チューリングマシンの流れ
  • チューリングマシンってコンピュータよりすごいんじゃなかったけ。
• より単純な機構
  • 有限オートマトン
  • プッシュダウンオートマトン*1
• NP困難な問題にも対応？

1.1.1 有限オートマトンとは

• 状態を持つシステムに応用できる
  • コンパイラの字句解析（なんだか詳しく説明）
  • キーワード検索（アルゴリズムでやる：やったっけ？）
  • 通信プロトコルとか使えます（TCP/IPみたいな）

例：

• 切り替えスイッチ
  • ONとOFFの2状態：行ったり来たり
• 特定文字列の認識
  • thenとかどーよ

以下数学基礎知識につき省略

1.5 オートマトン理論の中心概念

1.5.1 アルファベット

記号の空でない有限集合のこと
アルファベットは与えられて議論する。

1.5.2 文字列

アルファベット中の記号の有限列

• 空列
  • εで表す。長さ0の文字列である。
• 列の長さ
  • 記号の数。
• アルファベットのべき
  • ：アルファベットΣをk個並べてできる文字列のこと。εは幾ら並べても0個だから普通は並べない
  • ：アルファベットΣを並べてできる文字列全てを表す
• 連接
  • xとyを文字列としたとき、xyはxの文字列の後ろにyを並べたものである

1.5.3 言語

のとき、Lを(Σ上の)言語という
例：

• 英単語の集合
• Cプログラムの集合
• 空集合
• 空列だけからなる集合*2

アルファベットは有限集合であるが、言語は無限集合になることもありうる

1.5.4 問題

与えられた文字列が言語に属するかどうかを決定すること
例：与えられた文字列ｗを2進数で解釈したとき素数か？

2.1 有限オートマトンの直感的な説明(text p.40-)

電子マネーのプロトコルを例に挙げて説明
取りうる行動

• 客が支払いのため電子マネーを店に送る(pay)
• 客が電子マネーの取り消しを行う(電子マネーを銀行に送り客の口座に加えるよう要求する)(cancel)
• 店が商品を客に発想する(ship)
• 店が電子マネーを兌換する(電子マネーを銀行に送り店の口座に加えるよう要求する)(redeem)
• 銀行が暗号化された電子マネーを新たに作り、それを店に転送する(transfer)

*1:テープの代わりにスタックみたいな

*2:注意：空集合Φと空列{ε}は違う