無限状態オートマトンの説明

質問

教科書の以下の説明が1週間ぐらい何度も試みたのですが理解できません。

無限状態オートマトンとしては入力wに関する情報として系列wそのものを
状態qwとして覚えるものと考え、状態遷移関数をw∈Σ*,a∈Σにたいして
δ(qw,a)=qwaと定義する。
開始状態をqεとし、受理状態の集合として、F={qw|w∈L}と指定する。
このように指定したオートマトンにw=a1a2・・・anを入力すると、
qε→qa1→qa1a2→・・・→qa1・・・anと遷移し、w∈Lのとき、qwは受理状態
であるのでwは受理される。

宜しくお願いします。

回答No.1

root_16 · ベストアンサー

良く分かりませんが、
入力wが、a1, a2, a3, a4,・・・, anとされていて、
状態は系列wそのものを状態qwとして覚えるのであれば、
状態qwは
a1を入力した時点で
qa1
a2を入力した時点で
qa1a2
a3を入力した時点で
qa1a2a3
anを入力した時点で
qa1a2a3・・・an
です。
w∈Lのとき受理状態と定義しているので、
w∈Lであれば受理されます（変な書き方する教科書ですね）。

qε→qa1→qa1a2→・・・→qa1・・・anと遷移
の・・・の部分の勘違いかなと思い書きました。

お礼

回答ありがとうございます。

ちょっと考えて見ます