文脈自由文法と対応するPDAを取得するには？

Question

私はこの練習をどのように解決できるのか理解できません。

私は、次の入力を検証することができ、文脈自由文法を行う必要があります。

L={w € (0,1,2)* | w= 2^n 0^(m+1) 1^(m+n) with n>=0, m>0} 

はどうやって対応するPDAを作成することができますか？

私は、言語がプレフィックスプロパティを持たないので、PDAは空のスタックを受け入れることができないと思います。 それは正しいですか？

Answer 1

最初に文法を試してみましょう。私たちはそれのためのオートマトンを作ります。

実際に正規表現を含めてどのような文法でもCFGを作成する場合、文法が簡単に行うことができるいくつかの種類の簡単な言語を知っておくと便利です。文脈自由文法は、普通の文法ができることを簡単に行うことができ、入力にもマッチすることができます。これは、^ n b^nのような言語、パリドローム、マッチしたかっこなどが簡単であることを意味します。

このような問題を見てみると、これらのステレオタイプの言語があれば、その言語の文字列のすべてまたは一部がどのように見えるかを調べてみてください。この場合、a^n b^nにバリエーションがあります。私たちはこれを2回行う必要があります。

0 ^（m + 1）1^mから始めましょう。 CFGをこれで作れますか？さて、確かに。それは実質的にa^n b^nと同じです。ここでは、次のとおりです。

S := 0E 
E := 0E1 | - 

今、私たちは、n個の項に対処する必要があります：私たちは同数で、右に左に2と1を追加することができるはずです。これも簡単です：

S := 2S1 | S' 
S' := 0E 
E := 0E1 | - 

あなたは行っています。 CFGを取得するには、これらのことの定義に従って、ボトムアップまたはトップダウンのパーサーを簡単に構築できます。私たちは一からPDAを作ります。

私たちのPDAは2つを1つのループで受け入れる必要があり、2つをスタックにプッシュする必要があります。私たちは何回目に見たかを覚えておく必要があります。 0が見えるときは、新しい状態にして、ループ内で0を受け入れ続け、入力に見られる0のそれぞれに対してスタックに0を加えます。 1を見ると、新しい状態にして、1をループで受け取り、スタックから2または0のいずれかを削除する必要があります。実装の詳細を正しく取得した場合、最初の3つから分離した受け入れ状態で空のスタックを受け入れることができます。