Właściwość zamknięcia CFL

Języki bezkontekstowe to closed pod -

  • Union
  • Concatenation
  • Operacja Kleene Star

Unia

Niech L 1 i L 2 będą dwoma językami bezkontekstowymi. Wtedy L 1 ∪ L 2 jest również bezkontekstowa.

Przykład

Niech L 1 = {a n b n , n> 0}. Odpowiednia gramatyka G 1 będzie miała P: S1 → aAb | ab

Niech L 2 = {c m d m , m ≥ 0}. Odpowiednia gramatyka G 2 będzie miała P: S2 → cBb | ε

Połączenie L 1 i L 2 , L = L 1 ∪ L 2 = {a n b n } ∪ {c m d m }

Odpowiednia gramatyka G będzie miała dodatkową produkcję S → S1 | S2

Powiązanie

Jeśli L 1 i L 2 są językami bezkontekstowymi, to L 1 L 2 jest również bezkontekstowe.

Przykład

Unia języków L 1 i L 2 , L = L 1 L 2 = {a n b n c m d m }

Odpowiednia gramatyka G będzie miała dodatkową produkcję S → S1 S2

Kleene Star

Jeśli L jest językiem bezkontekstowym, wówczas L * jest również bezkontekstowy.

Przykład

Niech L = {a n b n , n ≥ 0}. Odpowiednia gramatyka G będzie miała P: S → aAb | ε

Kleene Star L 1 = {a n b n } *

Odpowiednia gramatyka G 1 będzie miała dodatkowe produkcje S1 → SS 1 | ε

Języki bezkontekstowe to not closed pod -

  • Intersection - Jeśli L1 i L2 są językami bezkontekstowymi, to L1 ∩ L2 niekoniecznie są bezkontekstowe.

  • Intersection with Regular Language - Jeśli L1 jest językiem zwykłym, a L2 jest językiem bezkontekstowym, wówczas L1 ∩ L2 jest językiem bezkontekstowym.

  • Complement - Jeśli L1 jest językiem bezkontekstowym, to L1 'może nie być bezkontekstowy.