閉包属性
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2015/04/29 04:57 UTC 版)
帰納言語は以下の操作について閉じている。すなわち、L と P を2つの帰納言語としたとき、以下の言語も同様に帰納言語である。 Lのクリーネ閉包 Lの準同型写像 φ(L) L と P の連結 和集合 共通部分 L の補集合 差集合 最後の属性は、差集合が和集合と共通部分から求められることから導出される。
※この「閉包属性」の解説は、「帰納言語」の解説の一部です。
「閉包属性」を含む「帰納言語」の記事については、「帰納言語」の概要を参照ください。
閉包属性
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2015/04/29 04:58 UTC 版)
帰納的可算言語は以下の操作について閉じている。すなわち、L と P を2つの帰納的可算言語としたとき、以下の言語も同様に帰納的可算言語である。 L のクリーネ閉包 L と P の連結 和集合 共通部分 帰納的可算言語は差集合や補集合の操作については閉じていない。差集合 L\P や L の補集合は帰納的可算言語となる場合もあるし、ならない場合もある。
※この「閉包属性」の解説は、「帰納的可算言語」の解説の一部です。
「閉包属性」を含む「帰納的可算言語」の記事については、「帰納的可算言語」の概要を参照ください。
閉包属性
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2017/03/10 07:44 UTC 版)
L と P を文脈自由言語、D を正規言語としたとき、以下も全て文脈自由言語である(閉じている)。 L のクリーネ閉包 L ∗ {\displaystyle L^{*}} L の準同型 φ(L) L と P の連結 L ∘ P {\displaystyle L\circ P} L と P の和集合 L ∪ P {\displaystyle L\cup P} L と(正規言語) D の積集合 L ∩ D {\displaystyle L\cap D} しかし、積集合や差集合に関しては閉じていない。これらの操作の具体的な内容については形式言語の情報工学的定義を参照されたい。
※この「閉包属性」の解説は、「文脈自由言語」の解説の一部です。
「閉包属性」を含む「文脈自由言語」の記事については、「文脈自由言語」の概要を参照ください。
閉包属性
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/07/07 15:06 UTC 版)
正規言語に対して、和集合、積集合、差集合といった演算を施した結果も正規言語である。正規言語の補集合(文字セットから生成される全文字列を全体集合とする)も正規言語である。正規言語の文字列を全て逆転させたものも正規言語である。正規言語の連結(ふたつの言語に含まれる文字列をあらゆる組み合わせで連結した文字列の集合)をしたものも正規言語である。「シャッフル」をふたつの正規言語に施した結果も正規言語である。正規言語と任意の言語の商集合も正規言語である。個々の操作の具体的意味については形式言語#定義を参照されたい。
※この「閉包属性」の解説は、「正規言語」の解説の一部です。
「閉包属性」を含む「正規言語」の記事については、「正規言語」の概要を参照ください。
- 閉包属性のページへのリンク