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 'は文脈自由ではない可能性があります。