私は、PDA が認識する言語を推測する方法を理解しようとしています。次の PDA を例にとります。トランジション チャートを作成してデルタ (トランジション) を把握することはできますが、それ以降はわかりません。これは宿題ではなく、本の例です。問題と遷移表は次のとおりです。
2341 次
1 に答える
0
表記を正しく読むと、L* のように見えます。ここで、L はループを 1 回だけ実行することで得られる言語です。ループを回ると、「c」、いくつかの「a」、同じ数の「b」、そして別の「c」が表示されます。したがって、L = ca^nb^nc であり、この PDA の言語は (ca^nb^nc)* です。
当然、これをチェックして、間違っていたら教えてください。また、これを理解するために私が行ったプロセスをよりよく説明することもできます.
編集: a^nb^n の取得元を説明します。
したがって、スタックは、スタックの一番下のシンボルZのみから始まります。したがって、最初は、スタックZ - (1, Z ) の状態 1 にあります。次に ac を確認し、状態 2 に遷移して、$ をスタックにプッシュします。だから私たちは (2, $ Z ) にいます。次に、a の n 個のインスタンスが連続して表示されるとしましょう。毎回、新しい c をスタックに追加し、状態 2 に戻ります。したがって、現在は構成 (2, c^n $ Z ) にあります。次に、b のインスタンスが表示されたとします。状態 3 に遷移し、スタックから ac を削除します。構成は (3, c^(n-1) $ Z）。$ がスタックの一番上に戻るまで、b のインスタンスを確認する必要があります。したがって、状態 3 では、(n-1) 個の b のインスタンスが表示され、それぞれが c の単一のインスタンスをスタックからポップします。これらの b のインスタンスを見た後、構成 (3, $ Z ) になります。最後に、c の別のインスタンスが表示され、$ がスタックの一番上にあるので、それをポップして、(1, Z )の初期構成で状態 1 に戻ることができます。
(a^n)(b^n) は、状態 2 で 'a' と同じ数の c のインスタンスをスタックに置き、状態 2 と 3 で同じ数のインスタンスをスタックから削除するという事実に由来します。 b のインスタンスを見ながら、スタックから c を取り出します。長さを表す n の選択は完全に恣意的です...これは、a と b のインスタンスの数が同じでなければならないことを示すためにのみ使用されます。受け入れ状態。
于 2011-10-19T13:31:51.777 に答える