| sys6.pdf sys.pdf sys-s.pdf 記事一覧 |
 有限オートマトンのアクセプタ |
#61: アクセプタ
記号列が所定の条件を満たしているか否かを識別する機械（アクセプタ）の例として，[#60] の順序回路の出力か否かを調べる機械の状態遷移図を上図に示しました．
※ (#60) の一部を付録（@60）にまわし，本文の内容を例題中心に変えました．(#) の内容もこれに連携しています．
補足：(1) 単に「有限オートマトン」というときは有限状態のアクセプタを指すことが多いようです．上図の式の説明は付録に回ってしまいましたので補足します．δは状態遷移関数，qp は初期状態，{qn, qp} は最終状態の集合です．最終状態とは入力記号列を読み終わったときの状態ですが，「読み終わった」ことの意味はδの定義域を Q×Σ から Q×Σ* に拡張した式で説明できます [0-1](第２章)．なお，δの定義域は Q×Σの部分集合でもよく，このときは遷移が未定義になったときも「読み終わった」と考えます（上図の状態遷移図で qe を省いてもよい）．
(2) 非決定性有限オートマトンの説明は省きました．
(3) 文字列の連接を積と考えると，空列は単位元に相当しますが，逆元は考えません [2-3]．
(4) 文字列は終端記号の記号列，アルファベットは終端記号の集合．生成文法には非終端記号も現れます [2-4]．
[2-1] 有限オートマトン - Wikipedia
http://ja.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3
[2-2] 決定性有限オートマトンと非決定性有限オートマトンについて詳しくのって
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1380950358
[2-3] 半群 - Wikipedia
http://ja.wikipedia.org/wiki/%E5%8D%8A%E7%BE%A4
[2-4] プログラミング言語論
http://www.cck.dendai.ac.jp/~koyama/pl/m/2011-02syntax.pdf
