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. W hierarchii Chomskiego 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 Chomskiego: 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 Chomskiego-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[1].
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ż
Przypisy
- ↑ An infinite hierarchy of intersections of context-free languages | SpringerLink [online], www.springerlink.com [dostęp 2017-11-24] (ang.).
Bibliografia
- John Hopcroft, Jeffrey Ullman: Wprowadzenie do teorii automatów, języków i obliczeń. Warszawa: Wydawnictwo Naukowe PWN, 2005. ISBN 83-01-14502-1.