オートマトン

これまで当然のように「オートマトン」と言う言葉を使ってきました。元々は自動人形、日本で言うと江戸時代に流行った「からくり人形」*1を指していました。それを計算機科学者がちゃっかりいただいて、今の状態と入力から次の状態(と出力)が決まる抽象的カラクリの名称にました。「有限」はあらかじめ有限種類の状態が決まっている型をいいます。それ以外に容量に制限のない外部記憶も状態として使える型があり、記憶の量やアクセス方法によって「線形有界オートマトン」「プッシュダウンオートマトン」などがあります。ここでは有限状態しかない有限オートマトンを扱います。前回のセルラーオートマタは有限オートマトンが並んだものです。…

有限オートマトン（Finite Automaton） プッシュダウンオートマトン（Pushdown Automaton） チューリングマシン（Turing Machine） オートマトンについて学ぶ時、私たちはまるで探検に出かけるような気持ちでいるといいですね。この探検では、計算の世界を旅して、コンピュータがどのように「考える」か、どのように「問題を解決する」かを理解していきます。さあ、この興味深い旅を始めましょう。 まず、オートマトンとは何か、簡単に言えば、これは「自動で動く機械」のことです。でも、私たちが今話しているのは、実際の機械ではなく、計算の問題を解くための抽象的なモデルです。この抽…

以下のWebサイトの「補足資料 (5)」に沿ってDFAを正規表現に変換するC#のメソッドを書こうとしているところ。 www.nue.ie.niigata-u.ac.jp 2ページ目の「GNFAの等価変換」は、さらっとななめ読みしただけだと分からなかったので、例2を自分で解いてみた。 まずは変換前のDFA と、変換後のGNFA 変換前のDFA M_{1}変換後のGNFA N_{1}

文字列処理でやってみた とりあえず ここ で以下の16個の正規表現を生成して、それらのルールを分析して、C#のメソッド作ってみたよ。 Regex01：文字列"0"を含まない任意の文字列とマッチする正規表現 Regex02：文字列"01"を含まない任意の文字列とマッチする正規表現 Regex03：文字列"012"を含まない任意の文字列とマッチする正規表現 ... Regex16：文字列"0123456789ABCDEF"を含まない任意の文字列とマッチする正規表現 github.comちなみに、生成して分析していた正規表現は以下。 ルールが見えやすいように、正規表現の縦を合わせてるけど、実際はスペ…

非決定性有限オートマトンの例 例3.1 偶数の2進数を認識する非決定性有限オートマトン ・値が0の場合は，一つの「0」を用いて表す(0は偶数として受理する)． ・値が0以外の場合は，最上位の記号が1であり，それ以外の記号は任意の個数の0と1とが続いた後，必ず0で終わる． このオートマトンは以下のようになる． 例3.2 文章中の記号列を認識する非決定性有限オートマトン () 入力中に「abc」が現れる記号列の集合を認識する有限オートマトンを考える．関数は以下の通りである． 決定性有限オートマトンへの変換 非決定性有限オートマトンは機械的な手順で決定性有限オートマトンに必ず変換できる． アルゴリズ…

非決定性有限オートマトン 非決定的動作とは，状態と入力の組に対して複数の状態遷移が定められているものである．このような動作をもつ有限オートマトンを非決定性有限オートマトンという．これに対して，状態と入力の組について高々一つしか状態遷移が定められていない．このような有限オートマトンを決定性有限オートマトンと呼ぶ． 例 このような言語を認識する二つの有限オートマトンを考える．1つの有限オートマトンの関数は より非決定性有限オートマトンである． 写像の一意性がない いま に対してもう一つの有限オートマトンは というように受理するので決定性有限オートマトンである． 例 この言語を認識する有限オートマト…

有限オートマトンの作り方 1. 条件をみたす有限オートマトンに必要な状態を考える(入力に対する状態の把握)． 2. 各状態に対して，すべての入力に対する状態遷移を考える． 特定の記号を認識する有限オートマトン とする．このとき，記号列が出現すると受理状態になる有限オートマトンを考察する．たとえば入力記号列が の場合，4文字目のが入力された後の状態と13文字目のが入力された後の状態は受理状態となり，その他の場合は受理状態とはならない．換言すれば言語は 入力がの場合：に遷移 入力がの場合：のまま 入力がの場合：のまま 入力がの場合：に遷移 入力がの場合：に遷移 入力がの場合：に遷移 入力がの場合：…