Учебники

Собственность закрытия КЛЛ

Контекстные языки закрыты под –

  • союз
  • конкатенация
  • Клини Стар операция

союз

Пусть L 1 и L 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 ‘может не быть контекстно-свободным.