G1 の言語が G2 の言語のサブセットであるかどうかをチェックするアルゴリズムが必要です。(G1 と G2 が同じアルファベットを持つ 2 つの LL(1) 文法であり、その生成規則が A-->aB または A-->a のいずれかの形式であり、「a」が非イプシロンであると仮定します。解析アルゴリズムがあります。文字列に対して文法をチェックするが、別の言語に対してチェックしない.解決策を持っている人はいますか.
質問する
136 次
1 に答える
1
あなたの文法は正しいように見えます。したがって、アルゴリズムは文法を NFA に変換することです。これは簡単な 1 対 1 のマッピングです。次に、サブセット構築を使用して NFA を DFA に変換します。これらを A と B と呼びます。それらを分析して L(A) サブセットを決定するのは簡単ですか? ポンド）。たとえば、L(A) ==? を決定するためのよく知られた効率的なアルゴリズムがあるためです。L(B) を作成し、L(A) の交点 L(B) を受け入れる新しいマシン I(A,B) を構築し、計算するだけです。
( L(I(A,B)) ==? L(A) ) or ( L(I(A,B)) ==? L(B) )
于 2015-12-23T17:22:41.017 に答える