有限と無限の間で

昨日の続き。
だから、有限回の繰り返しは、そのループの中でチェックできない。ループから出た位置でチェックするしかない。

PUSH           /* JUMPの直後からの再実行をスタックに登録 */
...Bの展開...
JUMP           /* PUSHの位置に戻る */
CHECK_STATE

(有限回で停止するための処理は省いて書いた)
この位置のチェックでも、指数関数的な組合せ爆発を避けることはできる。

/...(A{0,100000}...B*...C{0,100000})*.../

上記の例の場合、A, Cの繰り返しについては、繰り返しの後にチェックを入れることで指数関数的な組合せ爆発は起こらないようになる。しかし、入力文字列が非常に長く、入力長に対して二乗オーダーの組合せになるパターンに対しては役に立たない。

/...A*B{0,100000}.../

これは、今のところ止むを得ないとして実装を進めるしかないと思っているが、何だかやっていることが間違っているような気もする。