FC2ブログ

非決定姓チューリングマシン


だれが始めにそうしたかはしらないけど
言語の構文解析にはチューリングマシンが使われる。
もちろん、ソフト的なアイデアとしてね。
まったく同じではないけど。

そうすると確かに非決定性の扱いが簡単になる。
たとえばや、簡単な例だと、
a b って言う文がaしてbする、
a = b はbしたものをaに入れる。

上の例はaを読んだ段階で実行してもいいはずだけど
下の例はaを実行しないから少なくとも
aのあと一文字は読んで見ないとわからんわけ。
非決定的に書くと
qinit -(a) -> q0 -(b)-> qfin
(a) -> q1 -(=)-> ...
となって同じaを読んだのに行き先は違うわけ。


関連記事

コメントの投稿

非公開コメント

a8
最近の記事
月別アーカイブ
ブログ内検索
グリムス
フリーエリア
リンク
RSSフィード