PDA（プッシュダウンオートマトン）は、その言語の任意の文字列wに対して、スタックの方向を最大でk回回転させる場合、k回転であると言われます。また、言語Lは、1ターンのPDAによって受け入れられる場合は線形であることもよく知られています。さて、正規言語は0ターンのPDAによって受け入れられる言語であるというのは本当ですか？
質問する
206 次
1 に答える
2
はい、有限オートマトンは、スタックがまったく使用されない
一種と考えることができます 。0-turn PDA
オートマトンの 2 つの連続した説明で、スタックがそれぞれ上下する場合、PDA はターンを実行すると言われています。そして、すべての正規言語について、文字列の受け入れの最後でPDA空にする a を構築できます。PDS
また、正規言語は、チョムスキー分類(右線形または左線形) の線形言語のサブセットです。
于 2012-12-14T06:09:46.987 に答える