文脈依存文法から線形限定オートマトンに移行するアルゴリズムはありますか？

Question

私はLBA（linear bounded automata）を研究しています。いくつかのexersiseを解決する方法を把握しようとしています。

したがって、LBAにContext-sensitive文法を指定する簡単な方法があるのだろうかと思います。

これは、LR文法からDFA（決定論的有限オートマトン）に移行する方法のように考えています。文脈依存文法は、任意の縮小プロダクションルールを持っていないので、事前

Answer 1

で

おかげで、あなただけの徹底的な検索を使用することができます。

ストリングからは、元に戻すプロダクションを非確定的に選択できます。これは、入力の長さを増やすことはできません。空の文字列に到達するか（その場合は受け入れる）、またはプロダクションを元に戻すことができなくなるまで（この場合は拒否する）繰り返します。

これはスケッチですが、詳細の記入は簡単です。