問題タブ [pushdown-automaton]

FSM の正式な記述方法は覚えていますが、PDA の記述方法は少し異なります。丸で囲んだ部分を説明できる人はいますか？私は通常、よくメモを取りますが、ノートや他の場所でこれについて何かを見つけることができないようです. どんな助けでも大歓迎です。

開始状態、受け入れ状態、アルファベットの入力、その他すべてを把握する方法を知っています。しかし、PDA の遷移関係をどのように開発するのでしょうか? FSM の場​​合、(q0,a),q1) は、q0 から開始して a を取得すると、q1 に移行することを意味します。しかし、(S,a,e),(S,a) とはどういう意味ですか? (S は開始状態、e はイプシロン)

_{L を受け入れるNPDA}aの遷移グラフを描くには、 を読み取り、を書き、a右に移動してから同じことを行うことで、bこの問題を開始できると思います。動き。しかし、どうすれば を手に入れることができるのでしょうか?bbn-1

私はうまくいくと思うものを持っていますが、私はこれを自分自身に教えているので、誰かがどこで正しく行うことができるかを教えnてくれるかもしれません.n-1

編集：

しかし、今はこれで終わりです -

その言語 L を受け入れる NPDA の 2 つの状態で遷移グラフを描きたいとしましょう。また、この NPDA はちょうど 2 つの状態を持つとしましょう。これについての私の考えは、最初の状態ですべてを行い、2番目の状態をグランドフィナーレとして使用することです. そのようです：

しかし、ラムダ遷移が結果になるq1かどうか、またはこれを行うためのより良い方法があるかどうかはわかりません。これを自分自身に教えようとしているので、より良い方法がある可能性があります。おそらく、誰かが私をここで軌道に乗せることができますか?

Regular Grammarsに対応するFinite State Acceptorsものがあることを知りましたRegular Expressions。

と同等の変換はありContext Free Grammarsますか? 私が知る限り、文脈自由文法はPush Down Automata何に対応するもので表すことができますか?

これから私の心を片付けてくれる人に感謝します。