問題タブ [pushdown-automaton]

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

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

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

XSSセーフな文字列補間スキームの概念実証をまとめようとしています。

置換された文字列が与えられた場合、

それをリテラル部分と置換("Hello<b>" planetoid "</b>!")に分割してから、ステートマシンをリテラル部分に対して左から右に実行したいと思います。（上記の）補間値に達したときplanetoid、状態から適切なエスケープ関数に到達できる必要があります。

lex / yacc / bisonを使用してステートマシンを導出し、文法のラベルを出力状態に関連付ける方法の例を知っている人はいますか？javascriptで使用できるステートマシンを派生させ、PHPの基盤となる文字列実装を置き換えようとしています。

これを行う理由はここに記載されています。

乾杯、マイク

実数を決定する NFA はありますか?

これをPDA用にコーディングしたいと思います。C#でそれを行うにはどうすればよいですか?

このオートマトンの遷移関数を構築するのに行き詰まっています。

aごとに1をスタックし、bごとにアンスタックする必要があると思います

c の数は ab ペアの数に等しいので、遭遇する b ごとに 0 をスタックする必要があると思います。問題は、1 のスタックを解除して 0 を同時に追加するにはどうすればよいかということです。

アルファベット：a、b、c私は受け入れるPDAを定義しようとしています

受け入れられる文字列は次のとおりです。＃abc＃; ＃aabbcc＃; ＃aaabbbccc＃; ＃abbccc＃; ＃aaabbc＃などa、b、cの数は必ずしも同じではありません。

一番右の黒いスペースでプッシュダウンオートマトンの頭を開始します。

通常、私はPDAを列に書き込みます。

等々...

アルファベット：0、1

各文字を反転する反転を考えてみましょう: 0 -> 1; 1 -> 0 したがって、w = 0011 の場合、w-flip = 1100

逆順は逆順の文字であると考えてください。したがって、w = 01101 の場合、w-reverse = 10110 です。

今、私は文字列 w を受け取り、w を印刷する PDA を作成しようとしています (w-flip-reversed)

したがって、これは次のように出力されます: "011001"

# はブランク文字と見なしてください。したがって、文字列は #011# で始まります

遷移表は次のようになります。

等々

何か案は？

コンテキストフリー言語をプッシュダウンオートマトンに変換するためのアプレットまたはプログラムをオンラインで見つけることができません...どんな助けでも大歓迎です。

この初心者の質問で申し訳ありませんが、友人にそれが可能かどうかを伝えるために、簡単な回答が必要です.

決定論的有限オートマトンをプッシュ ダウン オートマトンに変換するアルゴリズムを探しています。

どんな助けでも感謝します。

ありがとう！