問題は、与えられた文脈自由文法Gからlとrの間の長さのすべての文字列を生成するアルゴリズムを実装することです。
私は単純なアプローチを思いつきました: 文法グラフで BFS を実行し、状態を記憶します。ただし、いくつかの再帰ルールでは失敗します。
(1) S -> 0 | SSS | λ
ルールには λ (空の文字列) を含めることができるため、文字列の最大長を単純に制限することはできません。(例: (1) をl = 1で 実行r = 2すると、私の実装では 0 のみが出力されます)
また、適用されるルールの最大数を制限しようとしましたが、明らかに間違っています。
アルゴリズムを制限または変更して、無限ループに陥らず、正しく機能するようにするにはどうすればよいですか?