決定性属性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/03/10 07:44 UTC 版)
文脈自由言語についての以下の問題は決定不能である。 等価性: 2つの文脈自由文法 A と B が与えられたとき、 L ( A ) = L ( B ) {\displaystyle L(A)=L(B)} か? L ( A ) ∩ L ( B ) = ∅ {\displaystyle L(A)\cap L(B)=\emptyset } か? L ( A ) = Σ ∗ {\displaystyle L(A)=\Sigma ^{*}} か? L ( A ) ⊆ L ( B ) {\displaystyle L(A)\subseteq L(B)} か? 文脈自由言語についての以下の問題は決定可能である。 L ( A ) = ∅ {\displaystyle L(A)=\emptyset } か? L(A) は有限か? メンバーシップ: ある単語 w を与えたとき w ∈ L ( A ) {\displaystyle w\in L(A)} か?（メンバーシップ問題は多項式時間で決定可能である。CYK法を参照されたい）
※この「決定性属性」の解説は、「文脈自由言語」の解説の一部です。
「決定性属性」を含む「文脈自由言語」の記事については、「文脈自由言語」の概要を参照ください。
ウィキペディア小見出し辞書の「決定性属性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 決定性属性のページへのリンク
