2

私は PDA のテストのために勉強していて、次の言語を認識するプッシュダウン オートマトンを設計する方法を知りたいです。

L = {a^max(0,n-m)b^n a^m| n,m >=0}

n-mが より大きいかどうかを認識する遷移関数を設計するにはどうすればよい0ですか?

また、このレベルの演習問題が解決されたコース教材があれば、リンクを貼ってください。

4

3 に答える 3

2

スタックの一番上の値に基づいて、現在の状態からどこに行くかを決定できます。スタック上のシンボルを使用して、解析の状態に関するメモを保持します。

これがどのように機能すると思いますか： これは入力から読み取られたシンボルであり、これはスタック上のシンボルです。スタックの一番下のシンボルXは、 n <= m がXとZを混同しないことを意味します。これは、スタックの最初のシンボルであり、スタックがいつ空になるかを判断するのに役立ちます。

このソリューションにはおそらくいくつかの問題がありますが、全体的なアプローチは正しいはずです。

...そしてあなたのテストで頑張ってください:-)

最初に、文字列の先頭からすべてのa記号を読み取り、それぞれのスタックにAを追加するか、aがない場合はXをプッシュします。

次に、すべてのb記号を読み取ります。

  • スタックが空 ( Zが一番上)、Bが一番上、またはXが一番上にある場合、別のBをスタックにプッシュします。
  • スタックの一番上にAがある場合は、それを削除します。

最後のステップは、最後の a記号を読み取ることです。

  • スタックにBがある場合は、それを削除します。
  • スタックにXがある場合は、そこに保持します
  • スタックが空 ( Zが一番上) の場合、これは文字列の最後でなければなりません

別の編集：

上記が明確でない場合は申し訳ありません...私はそれを形式化しようとします。

受け入れ状態は (4) と (5) で、開始状態は (1) です。そしてそれは非決定論的です

遷移規則:

状態 (1) :シンボルの最初のバッチを読み取る

  • ( 1 ) Z / AZ -> (1)
  • ( 1 ) A / AA -> (1)
  • (1) イプシロン; A / A -> (2)
  • (1) イプシロン; Z / Z -> (2)

状態 (2) : b個のシンボルを読み取る

  • (2)イ．Z / BZ -> (2)
  • (2)イ．X / BX -> (2)
  • (2)イ．B / BB -> (2)
  • (2)イ．A / イプシロン -> (2)
  • (2) イプシロン。B / B -> (3)
  • (2) イプシロン。X / X -> (3)
  • (2) イプシロン。Z / Z -> (3)

状態 (3) : 最後の a sを読み取る

  • ( 3 ) B / なし -> (3)
  • (3) イプシロン。X / X -> (4)
  • (3) イプシロン。Z / Z -> (5)

状態 (4) : m > n の場合、末尾の a s

  • ( 4 ) X / X -> (4)

状態 (5) は、m < n の場合に正確な文字列を受け入れるためのものです。

（そして、完全に明確にするために-状態の方法がなく、読み取りカーソルが単語の最後にない場合、その単語は受け入れられません）

これは、スタックシンボルXの代わりに追加の状態を使用することで少し簡単になる可能性がありますが、自分でできると思います:-)

于 2009-06-28T16:06:27.770 に答える
1

おそらく最も簡単な方法は、その言語の文法を書き、そのための PDA を作成することです。文法を書く最も簡単な方法は、最初にその「最大」に基づいて言語を分割し、何が起こっているのかを簡単に確認することです

L = L1 \union L2
L1 = { b^n a^m | m >= n >= 0 }
L2 = { a^(n-m) b^n a^m | n >= m >= 0 }

L1 と L2 を少し単純にするために書き直します ( j = mn, k = nm )

L1 = { b^n a^n a^j | j,n >= 0 }
L2 = { a^k b^k b^m a^m | k,m >= 0 }

これらは非常に単純な文法に変わります

L1 := BA A
L2 := AB BA
AB := a AB b | \epsilon
BA := b BA a | \epsilon
A  := a A | \epsilon
L  := L1 | L2

それらから PDA を作成します -- 自動化されたツールを使用するのが最も簡単ですが、すべての作業を表示する必要がある場合は手動で行うことができます

于 2009-09-18T23:26:10.180 に答える
0

言語 L は、Chompsky 階層の文脈依存言語またはタイプ 1 言語であると思います。私は間違っているかもしれません。

言語L1 = { a^n b^n c^n : n >= 1 }はタイプ 1 言語の例であり、これはかなり似ています。私にはひっかけ問題のように聞こえます。L を認識または生成できるタイプ 2 または文脈自由文法または PDA はないと思います。

于 2009-07-25T04:52:20.507 に答える