コンテキストフリーの文法と対応する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を作成する場合、あらゆる文法、実際には通常の表現を含む - 文法が簡単にできるいくつかの種類の単純な言語を知ることは役立ちます。コンテキストフリーグラマーは、通常の文法ができることを非常に簡単に実行でき、入力と一致させることもできます。これは、^nb^n、パリンドロム、マッチングされた括弧などのような言語が簡単にできることを意味します。

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

0^（m+1）1^mから始めましょう。これのためにCFGを作ることはできますか？まあ、確かに;それは実質的にa^nb^nと同じです。ここにあります：

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

次に、n用語に対処する必要があります。左に2を追加し、右に1を追加できるはずです。これも簡単です：

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

そこに行きます。 CFGを取得するには、これらのことの定義に従って、ボトムアップまたはトップダウンパーサーを簡単に構築できます。ゼロからPDAを作ろうとします。

私たちのPDAは、ループで2を受け入れ、スタックにそれぞれ2を押し込む必要があります。結局のところ、私たちが見た数を覚えておく必要があります。 0が表示されたら、新しい状態に移動し、ループで0を受け入れ続け、入力に見られる各0のスタックに0を追加する必要があります。 1が表示されたら、新しい状態に移動し、ループで1を受け入れ、スタックから2または0のいずれかを削除する必要があります。実装の詳細を正しく取得した場合、最初の3つとは別の受け入れ状態の空のスタックで受け入れることができます。