オートマトンについて1 | 宇宙とブラックホールのQ&A (ameblo.jp)
オートマトンについて2 | 宇宙とブラックホールのQ&A (ameblo.jp)
---------------------------------------------
非決定性オートマトンの遷移関数 δ は、決定性のときと同様、語の入力に関する関数に拡張されます。
・δ^(q, ε) ＝ {q}，
・δ^(q, aw) ＝ ∪p∈δ(q, a) δ^(p, w)．
また、A⊂Q に対して、δ^(A, w)＝ ∪ q∈δ(q, a) δ^(q, w) とおきます。
次は、非決定性オートマトンが受理する語と言語です。
定義：非決定性有限オートマトン M が語wを受理するのは、δ^(Q0,w )∩F≠∅ となるとき、つまりある初期状態から出発してある終了状態に到達する過程があるときをいう。
M によって受理される言語は次のように定義される。
L (M ) ＝ { w∈Ω*：δ^( q0, w) ∩F≠∅ }．
それでは、非決定性有限オートマトンの受理する言語は決定性有限オートマトンのそれと異なるのでしょうか？
この点に関しては、次の定理があります。
定理4：非決定性オートマトン M に対する L (M ) は正則言語である。
すなわち、L (M ) を受理する決定性オートマトンが存在する。
証明：非決定性オートマトン M ＝( Q, Ω, δ, Q0, F ) に対し、決定性オートマトン M ‘ ＝( Q‘, Ω, δ‘, q0‘, F‘ ) を次のように定義する。
Q‘ ＝ P (Q)，
δ’ (A, s ) ＝ ∪ q∈A δ(q, s ) (ただし、A∈Q’ )，
q0’ ＝ Q0，
F ’ ＝ { A∈Q’：A∩F≠∅ }．
すると、δ’^( q0’, w ) ＝ δ^(Q0, w ) が簡単にいえるので、L (M ’) ＝L (M ) も容易にわかる。 ／／
ネタ本(田中著)をほぼ丸写ししたのですが、「簡単にいえる」「容易にわかる」といわれても「分からないよ」という方もいるでしょう。
そこで、例示です。
例３：語 01 と 011 を繰り返してできる言語 (01+011)* を受理する最も簡単な非決定性オートマトンと、それと同等な決定性オートマトンを求める。
L (M ) ＝ { 01, 011, 0101, 01011, 01101, 010101, 011011, … }
どちらも遷移図で示します。
・非決定性オートマトン
↘ 0 1 ここで、左上の矢印↘は初期状態を表し、
((0)) ⇄ (1) → (2) 二重括弧 (( )) は終了状態を表す。↻
↑ 1 │
└───-──┘1
状態 (0) のときに1の入力、(1) のときに0の入力、(2) のときに0の入力があっても、行き先がないので次の状態は存在しない。
・決定性オートマトン
↘ 1 不要な状態は省く。具体的には ({2}), ({0, 1}), ({1, 2}),
(({0})) ←─ (({0, 2})) ({0, 1, 2}) の4つ。
1↓ 0 ↘ 1⇅0
↻ (∅) ←── ({1})
0,1 0
終了状態は、(({0})) と (({0, 2})) の2つ。
非決定性で行き先がない場合は、決定性では空集合状態 (∅) に向かうものとする。
決定性での状態の単元集合は非決定性の各状態に対応する。つまり、左上の (({0})) は非決定性の ((0)) に、右下の ({1}) は (1) に対応する。
(1) のときに1の入力があると、((0)) と (2) の両方に遷移し得るので、右上の (({0, 2})) となる。
(2) のときに1の入力があると ((0)) に遷移し、(0) のときに 0 の入力があると (1) に遷移するので、それらにより (({0, 2})) からの遷移が決まる。
定理5： Ω上の正則言語に関して、以下が成り立つ。
(1) ∅ は正則言語である。
(2) 任意の a∈Ω に対して {a} は正則言語である。
(3) A, B が正則言語ならば、 A∪B も正則言語である。
(4) A, B が正則言語ならば、 A・B＝{v・w：v∈A, w∈B} も正則言語である。
(5) A が正則言語ならば、 A*＝{w1w2…wn：wi∈A} も正則言語である。
証明：(1), (2) は明らか。(3) は先に証明済み。
(4)；Aを受理するオートマトンの遷移図の終了状態から、Bを受理するオートマトンの遷移図の初期状態に矢印を引いたものは、A・B を受理するオートマトンの遷移図となる。
(5)：Aを受理するオートマトンの遷移図の終了状態から初期状態に矢印を引けば、それがA*を受理する非決定性オートマトンの遷移図となる。 ／／
定理5によれば、各 a∈Ω に対する {a} から、∪, ・, * を用いて定義される言語は正則言語となります。
{a} を単に a と書き、・ を省略し、∪ を ＋ で置き換えてできたものを正則表現(regular expression)（または正規表現）といい、計算機関連の言語を定義する際に広く用いられています。
例えば、{a}・({a}∪{b})* は a(a+b)* と書かれます。
定理6（クリーネ）： 定理5の(1)～(5) の5条件を満たす最小のクラスは、正則言語のクラスである。
証明：任意のオートマトン M ＝( Q, Ω, δ, q0, F ) に対し、その受理言語 L が正則表現をもつことを示す。
Q ＝ { q0, q1, …, qn } とし、オートマトン M i,j ＝( Q, Ω, δ, qi, {qj} ) で受理される言語を L i,j とする。
さらに、 M i,j が計算途中で（最初と最後を除いて） { q0, q1, …, qn } 以外の状態を通らずに受理する言語全体を L i,jk とおく。
また、便宜的に k＝－1 のときに L i,j－1 ＝{a：δ(qi, a)＝qj } とおく。
任意の i, j に対して L i,jk が正則表現をもつことを、k≧－1 についての帰納法で示す。
L i,j－1 は記号の有限集合なので、正則表現をもつ。
一般の k≧0 に対しては、
L i,jk ＝ L i,jk－1 ＋L i,kk－1 (L k,kk－1)* L k,jk－1
となるから、やはり L i,jk も正則表現をもつ。
最後に、受理言語 L ＝ ∪ j∈F L 0,jn なので、L も正則表現をもつ。／／
オートマトンについては今回で終わりです。
次はチューリング機械の予定ですが、いつになるかは分かりません。
★ 昨日と本日、藤井聡太名人に豊島将之九段が挑戦する第82期名人戦七番勝負の第2局が、千葉県成田市「成田山 新勝寺」で行われ、形勢が何度も逆転する熱戦となりましたが、最後は126手で名人の勝ちとなりました。叡王戦に続けてタイトル戦で初めての2連敗になるかと心配しましたが、さすがの終盤力でした。これで名人から見て2勝0敗、あと2勝で名人防衛です。
★★ 今日のロジバン 不思議の国のアリス192
.i mi kucli lo du’u xu kau da galfi mi ca lo nicte
あたし、夜の間に変わっちゃったのかしら。
kucli ： 好奇心がある/興味を覚える，x1は x2に対して；x1は詮索好き [生命・感情]
galfi ： 改変する/変える，x1に x2を x3に。-gaf-, -ga’i- [動作・物体操作] 「cenba」と違い、他動的で、結果が含意される
nicte ： 夜だ，x1は x2(日)の x3(場所)における；x1は夜行性だ。-cte- [時間・日]
アリスの自問自答が続きます。
主述語は kucli で、そのx1は mi 、x2は命題抽象節 { lo du’u … } です。
抽象節内は、 xu による真偽疑問を kau で間接疑問にしています。
英語の原文は “ I wonder if “ です。
主述語は galfi 「変える」で、そのx1が da 「何か」、x2が mi です。
後ろから間制句 { ca lo nicte } が掛かっています。
galfi は本ブログ初出ですが、これほど一般的な語根gismu をあまり見かけないというのは不思議です。他の言い方がいろいろあって、そちらが便利だからでしょうけど。
出典は、