4

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

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

4

1 に答える 1

8

スタックが20アイテムに制限されているPDAは、DFAと同等です。これがその証拠です。

  1. 任意のPDA-20を使用すると、同等のDFAにすることができます。|S|であるスタックアルファベットSを考えてみましょう。= N.スタックの最下部のシンボルZもあります。追加のシンボル-を想像します。これは、「未使用」を表すスタックにも含めることができます。スタックは、x =-* S*Zの形式の文字列と同等になります。ここで|x| = 20、すべての場合。スタックへのプッシュは、-の出現を置き換えることで構成されますが、ポップは、LIFOの方法で他のシンボルを-で置き換えることで構成されます。現在、PDA-20のスタックには（N + 2）^20の可能な構成があります。DFAを構築するには、この係数によってDFAの各状態を複製し、スタックの新しい構成を反映するDFAの状態への遷移を設定します。こちらです、

  2. 任意のDFAを取得すると、同等のPDA-20にすることができます。単にスタックを使用しないでください。DFAと同じ言語を受け入れるPDA-20があります。

証明の最初の部分を説明するために、状態A、B、C、...、Z、および多くの遷移を備えたPDA-5について考えてみます。入力アルファベットが{0、1}であるとしましょう。次に、2 ^ 5=32の異なるスタック構成があります。このPDA-5に相当するDFAは、状態A1、B1、...、Z1、A2、B2、...、Z2、...、A32、B32、...、Z32を持つ可能性がありますが、オリジナルと同じ数のトランジション。元のPDA-5の移行により、スタックが状態Rの構成＃2から構成＃17に、マシンが状態Fに移行した場合、DFAは状態R2から状態F17に移行します。

于 2012-01-13T18:10:30.980 に答える