Loading article…
形式言語理論では、決定性文脈自由言語( DCFL ) は文脈自由言語の 適切なサブセットです。これらは、決定性プッシュダウンオートマトンによって受け入れられる文脈自由言語です。DCFL は常に一義的であり、つまり一義的な文法を受け入れます。非決定性で一義的な CFL もあるため、DCFL は一義的な CFL の適切なサブセットを形成します。
DCFL は線形時間で解析できるため、実用上非常に興味深いものであり、また DCFG のさまざまな制限された形式は、単純で実用的なパーサーを許容します。そのため、DCFL はコンピューター サイエンスの分野で広く使用されています。
説明
DCFL の概念は、決定論的プッシュダウン オートマトン(DPDA) と密接に関連しています。プッシュダウン オートマトンを決定論的にすると、その言語能力は 低下します。プッシュダウン オートマトンでは、異なる状態遷移の選択肢を選択できなくなり、結果としてすべての文脈自由言語を認識できなくなります。[1] 明確な文法が常に DCFL を生成するわけではありません。たとえば、0 と 1 のアルファベットの偶数長回文の言語には、明確な文脈自由文法 S → 0S0 | 1S1 | ε があります。この言語の任意の文字列は、最初にすべての文字を読み取らなければ解析できません。つまり、プッシュダウン オートマトンでは、半解析文字列のさまざまな長さに対応するために、代替状態遷移を試す必要があります。[2]
プロパティ
決定性文脈自由言語は、決定性チューリングマシンによって多項式時間とO (log2n ) 空間で認識できる。したがって、DCFLは複雑性クラスSCのサブセットである。[3]
決定性文脈自由言語の集合は、以下の演算に対して閉じている: [4]
- 補体
- 逆準同型
- 正規言語による正しい商
- pre: pre( ) は、 にも属する適切な接頭辞を持つすべての文字列のサブセットです。
- min: min( ) は、 内に適切な接頭辞を持たないすべての文字列のサブセットです。
- max: max( ) は、 内のより長い文字列の接頭辞ではないすべての文字列のサブセットです。
決定論的文脈自由言語の集合は、以下の演算に対して閉じていない: [4]
重要性
このクラスの言語は、非決定性文脈自由言語よりもはるかに効率的に解析できるため、コンピュータサイエンスにおいて実用上非常に重要です。決定性プッシュダウンオートマトンでは、プログラムの複雑さと実行時間が、非決定性のものに比べて大幅に少なくなります。単純な実装では、後者は非決定性ステップが発生するたびにスタックのコピーを作成する必要があります。文脈自由言語のメンバーシップをテストする最もよく知られているアルゴリズムは、文字列の長さをnとすると、O( n 2.378 )時間かかるValiantのアルゴリズムです。一方、決定性文脈自由言語は、LR( k )パーサーによってO( n )時間で受け入れられます。[5]多くのコンピュータ言語がこのクラスの言語に属しているため、これはコンピュータ言語の翻訳にとって非常に重要です。
参照
参考文献
- ^ ホップクロフト、ジョン、ジェフリー・ウルマン(1979)。オートマトン理論、言語、計算入門。アディソン・ウェズリー。p. 233。
- ^ ホップクロフト、ジョン、ラジーヴ・モトワニ、ジェフリー・ウルマン(2001)。オートマトン理論、言語、計算入門第2版。アディソン・ウェズレー。pp. 249–253。
- ^ Cook, Stephen A. (1979 年 4 月 30 日 - 5 月 2 日)。「決定論的 CFL は多項式時間と対数二乗空間で同時に受け入れられる」。第 11 回ACM コンピューティング理論シンポジウム- STOC '79の議事録。アトランタ。pp. 338–345。doi :10.1145/800135.804426。
- ^ ab Hoogeboom、ヘンドリック;エンゲルフリート、ジュースト (2004)。正式な言語とアプリケーション。シュプリンガー・フェルラーク・ベルリン・ハイデルベルク。 p. 128.ISBN 978-3-642-53554-3。
- ^ Knuth, DE (1965年7月). 「左から右への言語の翻訳について」.情報と制御. 8 (6): 607–639. doi : 10.1016/S0019-9958(65)90426-2 .