- 977 名前：デフォルトの名無しさん mailto:sage [2017/11/23(木) 07:23:17.08 ID:NFzuGiE50.net]
- >>958
>ん〜、そのへんの学問的な分類はよう知らんけど、取りうる状態は有限でもバックトラックは起こるしそのためのスタックは要るんちゃう？
非決定性有限オートマトンは決定性有限オートマトンに変換できるので、
バックトラックが一切起こらない形に書き換えることは可能。
lexなんかだと、そのような変換を行ったコードを生成していたはず。
ただし、プログラム言語などで一般的に使われる正規表現は、
ここでいう正規言語を拡張したものなので、この限りではない。
