Automata-theory-cfl-closure-properties

CFLクロージャープロパティ

コンテキストフリー言語は、以下で*クローズ*です-

• 連合
• 連結 *Kleene Starオペレーション

連合

L〜1〜とL〜2〜を2つのコンテキストフリー言語とします。 その場合、L〜1〜∪L〜2〜もコンテキストに依存しません。

例

L〜1〜= \ {a ^ n ^ b ^ n ^、n> 0}とします。 対応する文法G〜1〜はP：S1→aAb | abになります

L〜2〜= \ {c ^ m ^ d ^ m ^、m≥0}とします。 対応する文法G〜2〜はP：S2→cBb |になります。 ε

L〜1〜とL〜2〜の和、L = L〜1〜∪L〜2〜= \ {a ^ n ^ b ^ n ^}∪\ {c ^ m ^ d ^ m ^}

対応する文法Gには、追加の生成規則S→S1があります。 S2

連結

L〜1〜とL〜2〜がコンテキストフリー言語である場合、L〜1〜L〜2〜もコンテキストフリーです。

例

言語L〜1〜とL〜2〜の和、L = L〜1〜L〜2〜= \ {a ^ n ^ b ^ n ^ c ^ m ^ d ^ m ^}

対応する文法Gには、追加のプロダクションS→S1 S2があります

クリーネスター

Lがコンテキストフリー言語である場合、L* もコンテキストフリーです。

例

L = \ {a ^ n ^ b ^ n ^、n≥0}とします。 対応する文法GにはP：S→aAb |が付きます。 ε

クリーネスターL〜1〜= \ {a ^ n ^ b ^ n ^} *

対応する文法G〜1〜には、S1→SS〜1〜の追加のプロダクションがあります。 ε

コンテキストフリー言語は、閉じられていません*

• 交差-L1とL2がコンテキストフリー言語である場合、L1∩L2は必ずしもコンテキストフリーではありません。
• 正規言語との交差-L1が正規言語であり、L2がコンテキストフリー言語である場合、L1∩L2はコンテキストフリー言語です。
• 補数-L1が文脈自由言語である場合、L1 'は文脈自由ではない可能性があります。