Język bezkontekstowy

Język bezkontekstowy (ang. context-free language) – 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.

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 bezkontekstowaEdytuj

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ładEdytuj

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

 
 

Słowo   możemy wyprowadzić:

 

Przykład – język DyckaEdytuj

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ściEdytuj

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 bezkontekstowegoEdytuj

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[1].

Podklasy klasy języków bezkontekstowychEdytuj

  • 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śćEdytuj

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łowaEdytuj

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 gramatykiEdytuj

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żEdytuj

PrzypisyEdytuj

  1. An infinite hierarchy of intersections of context-free languages | SpringerLink, www.springerlink.com [dostęp 2017-11-24] (ang.).

BibliografiaEdytuj