0

言語A= {a^mb^n |を認識する PDA を構築するタスクがあります。m > n} with ∑ = {a, b} ..どうすればいいのか少し混乱しています..この質問を解決するのを手伝ってくれませんか? ありがとう

4

2 に答える 2

0

問題に対する PDA の設計にすぐに飛びつくのではなく、まず問題を理解するようにしましょう。

特定の言語から生成できる可能性のあるいくつかの文字列は何ですか。
たとえば、そのような文字列は無限に存在する可能性があります-

  1. aab
  2. ああああ
  3. ああ...b
  4. あああ..bb

アイデアは、a の数が常に b の数よりも大きいことを確認することです。または、文字列内の b の数が、PDA によって受け入れられる文字列内の a の数を超えてはならないと言えます。

では、質問があります。

a の数が b の数より多いことを確認する方法

文字列のすべての 'b' に対して aをキャンセルし始める
と、次の結論が残されます。

  1. aの数とbの数が同じだった- キャンセル後に何も残っていなかった
  2. b の数が a の数よりも多い- キャンセル後、b はほとんど残っていません
  3. a の数が b の数よりも多い- キャンセル後、a がほとんど残っていませんでした

「質問」と上記のポイントとの関係を確立しようとすると、上記のポイント 3 に属する文字列が PDA で受け入れられる文字列であることがわかります。

次に、PDA を次のように定義します。

P = ({q0,q1,qf}, {a,b}, δ, {a,b,Z0}, q0, Z0, {qf})

遷移関数 (δ):

δ(q0, a, Z0) = (q0,aZ0)  
δ(q0, a, a) = (q0, aa)  
δ(q0, b, a) = (q1, Λ)  
δ(q1, b, a) = (q1, Λ) 
δ(q1, Λ, a) = (qf, Z0) 
δ(q1, b, Z0) = (q2, Z0)  
δ(q1, Λ, Z0) = (q2, Z0)

説明：

  1. 最初に a をスタックに格納します (q0 状態)
  2. 最初の b が検出されると、スタックから a をポップし、状態を q1 に変更します
  3. スタックから a をポップし続けます
  4. スタックから a をポップする b が残っていない場合は、状態を qf に変更して、文字列の受け入れを示します。（POINT No.3）
  5. b が残り少なく、スタックから飛び出す a がない場合、状態を q1 から q2(Trap) に変更します。（ポイントその２）
  6. ポップアウトするスタックに a が残っておらず、入力文字列に b も残っていない場合は、再度状態を q1 から q2(Trap) に変更します。（POINT No.1）
于 2015-05-16T19:23:52.900 に答える
0

ウィキペディアのプッシュダウン オートマトンのページにあるこの例を見てください。言語 { 0 n 1 n  | n  ≥ 0 }、つまり、いくつかのゼロの後に同じ数の 1 が続きます。これはあなたのタスクとまったく同じではありませんが、似ています。コース教材に基づいた説明を理解できますか? 必要な言語を認識するためにどのように変更しますか?

于 2011-03-26T07:29:33.763 に答える