勉強や趣味など、日々の生活で経験したことを発信します。プッシュダウンオートマトンをわかりやすく解説】形式言語とオートマトン2022-10-25こんにちはの方もこんばんはの方もようこそ、イカスミです。大学生、特に情報系学生の皆さん、形式言語の授業で、プッシュダウンオートマトンって何?となった経験はありませんか?この記事では、そんな方に向けて、情報系大学生の僕がプッシュダウンオートマトンについて解説したいと思います。この記事で解決できる悩みプッシュダウンオートマトンがわからないプッシュダウンオートマトンの問題が解けないこの記事では、こちらの参考書を基準としていますので、余裕がある方は手にとってみてください。リンクリンクプッシュダウンオートマトンとはプッシュダウンオートマトンは、有限オートマトンにスタックと呼ばれる記憶装置を付け加えたものです。有限オートマトンについては、こちらの記事で解説しているので、参考にしてみてください。【現役大学生が決定性有限オートマトンをわかりやすく解説します】形式言語とオートマトンこんにちはの方もこんばんはの方もようこそ、イカスミです。...続きを見る【現役大学生が非決定性有限オートマトンをわかりやすく解説します】形式言語とオートマトンこんにちはの方もこんばんはの方もようこそ、イカスミです。...続きを見るスタックとは、「先入れ後出し」の記憶装置です。データをスタックに入れ、最後に格納したデータから取出します。有限オートマトンとの違いプッシュダウンオートマトンは、スタックを用いて入力を記憶できるので、有限オートマトンよりも多くの言語を表現できます。状態遷移図も異なります。有限オートマトンはこのような状態遷移図でしたが、プッシュダウンオートマトンの状態遷移図はこのようになります。記述する記号が増えていますね。ここでは、λはεを表します。いう遷移関数は、入力が0、スタックの先頭記号が0の場合、スタックの先頭記号を取り除くことを表します。1:01は、入力が0、スタックの先頭記号が1の場合、スタックに1を加えることを表します。大体の場合、受理状態への遷移は、スタックが空の場合にε遷移で行われます。このように、プッシュダウンオートマトンの状態遷移図は、スタック記号の記憶・削除を上手く用いることが重要となります。例題を用いて、プッシュダウンオートマトンをわかりやすく解説します。例題:長さが偶数の回分を受理するプッシュダウンオートマトンの状態遷移図を示せ。長さが偶数なので、入力を半分に分けて考えます。前半の入力はスタックへの記憶、後半の入力はスタックの記号を削除するために用います。そのためには、次の3つの状態が必要となります。q0:前半の入力をスタックに記憶する状態q1:後半の入力を用いて、q1で記憶したスタック記号を削除する状態q2:受理状態q1では入力をスタックに記憶するので、遷移は自分自身に向かいます。q2ではスタック記号と入力が一致した場合、スタック記号を削除します。この操作を状態遷移図にすると、このようになります。次に、各状態をつなぎ合わせます。q1からq2への遷移は、ε遷移で行います。いうと、q1で入力の前半、q2で入力の後半を使うので、もし入力を使用してしまうと、q2で使用する入力が足りなくなってしまうからです。q3は受理状態なので、q2からq3への遷移は、スタックが空の場合にε遷移を行います。最終的な状態遷移図は、このようになります。q0で前半の入力を記憶し、ε遷移によりq1に遷移します。q1で後半の入力を用いてスタック記号を削除します。入力がない)、かつスタック記号が空の場合に、q2に遷移し、入力が受理されます。まとめこの記事では、プッシュダウンオートマトンについて解説しました。まとめると、プッシュダウンオートマトンは、有限オートマトンにスタックを付け加えたもの状態遷移図は、スタック記号の追加・削除を利用するこの記事が、皆さんの学習の参考になれば幸いです。最後まで読んで頂き、ありがとうございました。変数分離】解法を現役大学生が例題付きで解説こんにちはの方もこんばんはの方もようこそ、イカスミです。【チューリングマシン】情報系大学生がわかりやすく解説しますこんにちはの方もこんばんはの方もようこそ、イカスミです。大学生2023年1月29日(午後開催)のTOEICスコアが返ってきました1ヶ月以上前になりますが、2023年1月29日(午後開催)のTOEICスコアが返ってきました。いうことで、スコアを見ながら、振り返りをしようと思います。リーディングが終わらない!こんにちはの方もこんばんはの方もようこそ、イカスミです。3月19日午後開催のTOEICを受けてきました。前回同様、感想を書いていこうと思います。【オンライン授業で首が痛い!】対処法を教えますこんにちはの方もこんばんはの方もようこそ、イカスミです。実はそれ、放っておくと大変なことになるかもしれません。【チューリングマシン】情報系大学生がわかりやすく解説しますイカスミイカスミです。名前の由来は中学時代のあだ名から。情報系を専攻する大学4年生。趣味は映画鑑賞、散歩、ブログ(趣味にしたい)。日常生活で得た情報や大学の授業などを、雑記ブログとして発信します。Proレビュー】少しクセはあるが、いいパソコンです【単発バイト探しにオススメ】フルキャストについて解説!最近のコメント表示できるコメントはありません。趣味など、日々の生活で経験したことを発信します。