Język bezkontekstowy

Język bezkontekstowy () – język formalny taki, że istnieje niedeterministyczny automat ze stosem decydujący czy dany łańcuch należy do języka. Równoważnie, taki, że istnieje dlań gramatyka bezkontekstowa. W hierarchii Chomsky’ego jest zdefiniowany jako język typu 2.

Rodzina języków regularnych jest podzbiorem zbioru języków bezkontekstowych.
Każdy język bezkontekstowy jest językiem kontekstowym.

Języki bezkontekstowe mają ważne znaczenie w informatyce, m.in. w budowie kompilatorów; patrz analiza składniowa.

Gramatyka bezkontekstowa 
Każdy język bezkontekstowy jest generowany przez pewną gramatykę bezkontekstową. Nazwa ta bierze się od tego, że wszystkie jej reguły są postaci  gdzie  jest dowolnym symbolem nieterminalnym, i którego znaczenie nie zależy od kontekstu w jakim występuje, a  to dowolny (być może pusty) ciąg symboli terminalnych i nieterminalnych.

Do zapisu reguł można stosować notację Backusa-Naura.

Przykład 
Język słów postaci  jest generowany przez:
 
 

Słowo  możemy wyprowadzić:

Przykład – język Dycka 
Język „poprawnie rozstawionych nawiasów”, czyli takich wyrażeń, które mają tyle samo wystąpień znaku  i znaku  i w każdym prefiksie słowa jest nie mniej  od  (można sprawdzić, że takie warunki rzeczywiście są równoważne temu, że nawiasy są poprawnie rozstawione) jest generowany przez:
 
 
 

Słowo  można wyprowadzić:
 

Ten język nazywa się językiem Dycka. Ogólnie, możemy zdefiniować język Dycka  dla  możliwych rodzajów nawiasów (tj. nad alfabetem ) za pomocą gramatyki

Własności 
Podane poniżej własności mają charakter algorytmiczny, tj. pisząc, że język  jest bezkontekstowy, istnieje stała , istnieje język regularny  mamy na myśli także fakt, że można podać algorytm wyznaczający te obiekty, dostający na wejściu dane reprezentowane w efektywnej postaci. W efektywny sposób jest wykonywalna konwersja między gramatyką bezkontekstową a niedeterministycznym automatem ze stosem (w obydwie strony).

 Języki bezkontekstowe są zamknięte ze względu na konkatenację, sumę, domknięcie Kleene’ego, odbicie lustrzane i przecięcie z językami regularnymi: jeżeli  i  są językami bezkontekstowymi oraz  jest językiem regularnym, to językami bezkontekstowymi są zawsze     

 Postać normalna Chomsky’ego: każdą gramatykę bezkontekstową, której język nie generuje słowa pustego można sprowadzić do postaci, w której każda reguła ma postać  lub  gdzie  to symbole nieterminalne,  to symbol terminalny. Tę postać normalną wykorzystuje się w algorytmie CYK.

 Postać normalna Greibach: każdą gramatykę bezkontekstową, której język nie generuje słowa pustego można sprowadzić do postaci, w której każda reguła ma postać  gdzie  to symbol nieterminalny,  to symbol terminalny,  to ciąg (być może pusty) symboli nieterminalnych.

 Lemat o pompowaniu: Dla każdego języka bezkontekstowego istnieje takie  że każde słowo  tego języka długości większej od  można zapisać w postaci  gdzie  przynajmniej jedno z  i  jest niepuste, i dla każdego   należy do tego języka.

 Lemat Ogdena: dla każdego języka bezkontekstowego istnieje takie  że każde słowo  w którym oznaczymy więcej niż  symboli można zapisać w postaci  gdzie ilość oznaczonych symboli w  jest mniejsza od  przynajmniej jedno z  i  zawiera oznaczony symbol, i dla każdego   należy do tego języka. Lemat o pompowaniu jest szczególnym przypadkiem lematu Ogdena, w którym oznacza się wszystkie symbole.

 Twierdzenie Parikha: Niech  przyporządkowuje słowu wektor liczby wystąpień każdej litery w słowie (np.  dla ). Wówczas dla każdego języka bezkontekstowego  istnieje język regularny  taki, że  Przykład: dla  można wziąć 

 Twierdzenie Chomsky’ego-Schützenbergera: dla każdego języka bezkontekstowego  istnieje liczba naturalna  język regularny  nad alfabetem  oraz homomorfizm  taki, że  ( to język Dycka).

Przecięcie języków bezkontekstowych i dopełnienie języka bezkontekstowego 
Dopełnienie języka bezkontekstowego albo przecięcie dwóch języków bezkontekstowych nie musi być językiem bezkontekstowym.

Przykład: język  nie jest bezkontekstowy (co można wykazać korzystając z lematu o pompowaniu). Język ten jednak jest przecięciem dwóch języków bezkontekstowych  i 

Dopełnienie języka bezkontekstowego  nie jest językiem bezkontekstowym. Gdyby było, to po przecięciu z językiem regularnym  dostalibyśmy język bezkontekstowy (tymczasem dostajemy ).

Dla każdego  istnieje język, który można przedstawić jako przecięcie  języków bezkontekstowych, ale nie można przedstawić jako przecięcie  języków bezkontekstowych.

Podklasy klasy języków bezkontekstowych 
 Języki liniowe to języki, dla których istnieje gramatyka, w której po prawej stronie każdej reguły znajduje się co najwyżej jeden nieterminal. Nie każdy język bezkontekstowy jest językiem liniowym; za przykład może służyć 

 Języki bezkontekstowe deterministyczne to języki rozpoznawalne przez deterministyczny automat ze stosem. Są one zamknięte ze względu na dopełnienie i przecięcie z językami regularnymi. Nie każdy język bezkontekstowy jest językiem deterministycznym; za przykład może służyć  (Gdyby był on deterministycznym językiem bezkontekstowym, to jego dopełnienie przecięte z  –  również takie by było. Ale ten język nie jest nawet bezkontekstowy.)

 Języki jednoznaczne to języki, dla których istnieje jednoznaczna gramatyka bezkontekstowa – gramatyka, w której każde słowo może mieć tylko jedno drzewo wyprowadzenia. Przykładem języka niejednoznacznego jest

Rozstrzygalność 
W językach regularnych praktycznie wszystkie problemy decyzyjne są rozstrzygalne.
Nie jest to już jednak prawdą w językach bezkontekstowych.

Rozstrzygalne są takie problemy jak:
 czy dane słowo należy do danego języka (algorytm CYK wykonuje ten test w czasie ),
 czy istnieje jakiekolwiek słowo, które należy do danego języka,
 czy do danego języka należy co najmniej  słów,
 czy dany język zawiera nieskończenie wiele słów.

Nierozstrzygalne problemy to natomiast m.in.:
 czy istnieje jakiekolwiek słowo, które nie należy do danego języka,
 czy dane dwa języki są równe,
 czy jeden język bezkontekstowy jest podzbiorem drugiego,
 czy istnieje słowo wspólne dla danych dwóch języków,
 czy dany język jest jednoznaczny,
 czy dana gramatyka jest jednoznaczna.

Dowód nierozstrzygalności istnienia wspólnego słowa 
Pytanie czy przekrój 2 języków jest niepusty można zredukować do problemu odpowiedniości Posta – niech  oznacza -tą parę słów w systemie Posta.
Stwórzmy dwa języki bezkontekstowe  i 
  dla każdego  odpowiadającego parze słów w systemie Posta,
 
 
 

gdzie  są nowymi symbolami terminalnymi, niewystępującymi w żadnym  ani 

Wygenerowane słowo języka  składa się ze słowa wygenerowanego przez pierwszy język systemu Posta, oraz (odwróconego) znaczenia tego słowa:
 

Analogiczną postać mają słowa wygenerowane przez  Czyli jeśli istnieje słowo wspólne dla  i  to w systemie Posta, na podstawie którego zostały zbudowane, istnieje słowo rozwiązujące pozytywnie problem odpowiedniości w tym systemie.

Ponieważ jednak problem odpowiedniości Posta jest nierozstrzygalny, nierozstrzygalne jest też istnienie wspólnego słowa.

Dowód nierozstrzygalności jednoznaczności gramatyki 
Weźmy dwa jednoznaczne języki  i  o rozłącznych nieterminalach, i symbolach startowych odpowiednio  i  Zbudujmy następującą gramatykę o symbolu startowym 
 
 
 plus wszystkie produkcje obu języków.

Gramatyka taka jest jednoznaczna wtedy i tylko wtedy, gdy nie istnieje słowo należące jednocześnie do  i  Ponieważ dla każdego systemu Posta potrafimy zbudować jednoznaczne gramatyki (poprzedni dowód), rozwiązanie problemu jednoznaczności rozwiązywałoby problem odpowiedniości Posta.

A zatem problem ten jest nierozstrzygalny.

Zobacz też 
 parser

Przypisy

Bibliografia 
 

Języki formalne