CFGをNDPAに変換するルールはありますか？

Question

私はこの文法を使用してFAを定義する必要があります。

S -> aSb 
S -> c 
S -> dA 
A -> Sd 

は、どのように私は最初のルールと最後の1を管理していますか？ もう1つは、別の状態（最終状態）を作成し、Sとこの新しい状態をリンクしなければならないと思います。 3番目の代わりに、私は状態 "A"を作り、それを "d"を渡すことによってSにリンクしなければならないと思う。

Answer 1

CFGからPDAを入手するためのアルゴリズムがあります。例えば、トップダウンとボトムアップのパーサーを調べます。私は、PDAがCFGによって生成された言語を受け入れ、逆もまた同様であるという通常の証拠として考えているのは、そのような構成を使用することです。

代わりに、文法によって生成された言語を理解し、直接そのためのPDAを設計することができます。これは機械的ではありませんが、より簡潔なPDAを生成する可能性があります。あなたはこのルートを移動したい場合は、まず安全にそのための唯一の生産のRHSに置き換えることができ非終端Aを認識することによって文法を簡略化することができます。

S -> aSb 
S -> c 
S -> dSd // removed A -> Sd and replaced here 

はどのようにこの文法は動作しますか？

1. 2番目の製造では、中間にcがあります。
2. cの左右に一致するdがあります。
3. aは、bの右側にあるcと一致しています。
   1. 読むa sおよびd sはあなたがcが表示されるまで、次のよう

   A PDAは動作するはずです。スタックのすべてをプッシュします。 cが表示されたら、次の状態に進みますが、cは押さないでください。まで、スタックからa sおよびdの飛び出る

4. 読むb sおよびd秒、：一番上のスタック記号が入力と一致していません
   • 。クラッシュ。
   • シンボルがスタックに残っている状態で入力が不足しています。クラッシュ。
   • 入力が残っているスタックシンボルが不足しています。クラッシュ。
   • スタックを使い果たし、同時に入力します。受け入れてください。私たちは、空のスタックによってQ1に同意する場合は、これらの遷移は十分にある

     q s  x q' s' 
     ------------------------------ 
     q0 a,d,Z a q0 aa,ad,aZ 
     q0 a,d,Z d q0 da,dd,dZ 
     q0 a,d,Z c q1 a,d,Z 
     q1 a  b q1 - 
     q1 d  d q1 - 
     

     ：

はここ遷移表です。空のスタックを受け入れるか状態を受け入れる場合は、f(q1, Z, -) = (q2, Z)のような遷移を追加してq2を受け入れることができます。 PDAは非決定論的にそこに移行し、入力が枯渇しない限りクラッシュするだろう。