問題タブ [pushdown-automaton]

友人からプッシュダウン オートマトンについて質問されました。アバカ。私はいくつかの同様の問題を見ていますが、すべての問題には 0^a 1^a のような偶数が含まれていますが、現在は 3 つの値があります。その例を見つけましたが、質問をこれに変換できません。

どうすれば abacaa を変換できますか?

私はDPDAを実装する方法について読んでいて、次のインターネットアドレスでこのコードを見つけました：http：//code.zhoubot.com/ 、このcファイルは単純なプッシュダウンオートマトンを実装しています。オートマトンは、遷移関数と入力の説明を読み込み、入力に対して計算を実行してから、出力を出力します。

入力形式は次のようになります。e01：e0 $：000111：a：ad：aeeb $：b0eb0：b10ce：c10ce：ce $ de入力はセミコロン「：」で区切られ、最初のセクションは「入力アルファベット」、2番目は「スタックアルファベット」、次に「入力」、そして最後の全体が遷移関数です。

コンパイルしようとすると、コンパイラは次のエラーを通知します。

コードを理解しようとしているので、どうすればこのエラーを修正できますか？

明日の試験と教授は、その上にある質問を教えてくれます:)。

この図のコンテキストでは、L はイプシロン (空の文字列) であり、Z0 はスタックの空のシンボルです。

私は言語が生成する単語に関するいくつかのルールを決定する上である程度の進歩を遂げましたが、言語全体を特定することはできませんでした.

ありがとう！

文字列の括弧のバランスをチェックするために、次のプログラムを作成しました。

以下にデータの例を示します。

このプログラムは明示的な再帰の最も基本的な構成要素のみを使用するため、私がまだ気付いていない言語機能を含む、より短く、より高度なアプローチがあるかどうか疑問に思いました。

さて、いくつかの回答とコメント（および私自身の考え）から次の解決策を抽出しました。

私は、PDA が認識する言語を推測する方法を理解しようとしています。次の PDA を例にとります。トランジション チャートを作成してデルタ (トランジション) を把握することはできますが、それ以降はわかりません。これは宿題ではなく、本の例です。問題と遷移表は次のとおりです。

0 ^ m 1^nのpdaをどのように記述しますか。ここで|m| > = | n |; 0の数が1の数以上ですか？

私は考えていました：

• 1または0が表示された場合は、スタックにプッシュします
• 別の0または0の束が表示された場合は、それをスタックにプッシュします
• 1が表示された場合は、スタックにプッシュします
• その後に別の1が表示された場合は、スタックからポップします。

しかし、私はこれが正しいとは思いません。誰か助けてもらえますか？

スタックサイズがたとえば20アイテムに制限されているPDAで受け入れられる言語のタイプは何ですか？

私の見解では、保存する一時的なメモリがあるため、CFLのままである必要があります。

私は試験のオートマトンと正式な言語について勉強しています。言語を認識する PDA を設計する必要があります。

a ^ib ^2i i>= 1

解決策は次のようになると思いました：

テープから読み取った "a" ごとに 2 つの X をスタックします。次に、テープに "b" があり、スタックの一番上に X がある場合、スタックから 1 つの X をポップします。テープ、および Zo (スタック マーカーの下部) があり、文字列は受け入れられます。私の質問は: 1 つの計算ステップで 2 つの連続する X を積み重ねることができますか?

私は試験のオートマトンと形式言語を勉強しています。言語を認識するPDAを設計する必要があります。

私は少し考えがありますが、私はこれで立ち往生しています：

すべての「a」と各「a」が「A」をプッシュする最初の思考プロセス

だから私は解決策を考えました、しかし私は正しくないと思います、私は何か間違ったことをしていますか？

生成するCFGを次のオートマトンに書き込む必要があります。

私はこのような移行を知っています：

esは空の文字列を表します。

しかし、私は「c、a;a」のようなルールをどのように扱うかを知りません。誰でも私に助けを与えることができますか？ありがとうございました。

http://tonguim.free.fr/divers/automata.jpg