CFL閉鎖プロパティ

文脈自由言語は closed アンダー−

  • Union
  • Concatenation
  • クリーネ閉包の操作

連合

Lましょう1およびL 2 2つの文脈自由言語とします。そして、L 1 ∪L 2はまた、文脈自由です。

L 1 = {a n b n、n> 0}とします。対応する文法G 1は、 | AB S1→aAbを:Pを持っています

L 2 = {c m d m、m≥0}とします。対応する文法G 2は、 Pを持っています:S2→CBBを| ε

組合Lの1及びL 2、L = L 1 ∪L 2 = { 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 = { n個のB N、C 、M個のDのM }

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

クリーネ閉包

Lが文脈自由言語の場合、L *も文脈自由言語です。

L = {a n b n、n≥0}とします。対応する文法GはP:S→aAb |になります。ε

クリーネスターL 1 = { n個のb N } *

対応する文法G 1はSS追加制作S1→を持っています1 | ε

文脈自由言語は not closed アンダー−

  • Intersection − L1とL2が文脈自由言語である場合、L1∩L2は必ずしも文脈自由ではありません。

  • Intersection with Regular Language − L1が正規言語で、L2が文脈自由言語の場合、L1∩L2は文脈自由言語です。

  • Complement − L1が文脈自由言語の場合、L1 'は文脈自由ではない可能性があります。