0

次の言語を認識する JFLAP を使用してプッシュダウン オートマトンを作成する必要があります。

ここに画像の説明を入力

そのためにはどのような手順を踏む必要がありますか? そして、それはどのように機能しますか？

4

1 に答える 1

0

この質問はcs.stackexchange.comに適していると思いますが、とにかくソリューションを追加します。

例の形成

実際には見た目よりも簡単です。例として、オカレンスに次の値があると考えてみましょう。

n = 2
m = 3
p = 1

これにより、次の文字列を形成できるはずです。

a 2 b 3 c 1 a 1+3 b 2 = aabbbcaaaabb

論理的理解の形成

これから、追跡する必要があるシンボルを決定する必要があります。

  1. 外側のシンボルがn何度も発生することがわかっているため、ここをn,m ≥ 1追跡する必要があり、少なくとも1 回は発生する必要があります。n
  2. 少なくともq = p+mとmが発生することはわかっているので、 の発生を追跡する必要があります。m
  3. q = p+mの発生も保持する必要がある場合は、 と記載されているため、発生することもできないpことに注意してください。pp ≥ 0

正式な定義の形成

PDA Pを次の PDA にします。

P = (Q, Σ, Γ, τ, q 0 , Z, q 6 )

どこ：

  • Q は、d-PDA の状態のセットです。
  • Σ は、文字列を含む入力記号です。
  • Γ は、集合 Γ = {a,b} を含むスタック シンボルです。
  • q 0は初期 (開始) 状態です
  • Z はスタック シンボルです#
  • q 6は最終 (終了) 状態です

プッシュダウン オートマトンの作成

したがって、これから (JFLAP で) 次のオートマトンを作成できます。

JFLAP PDA

ここでは、上記のようにシンボルを追跡しているだけですが、ここで注意すべき重要なことはq3、トランジションが 0 以上のトランジションでcあるということです。

また、シンボル#をスタック シンボルとして使用します。

シミュレーション

上記の入力 ( aabbbcaaaabb) でこの PDA をシミュレートすると、次の結果が得られます。

シミュレーション

于 2016-09-19T11:34:04.333 に答える