Język bezkontekstowy

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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

Słowo możemy wyprowadzić:

Przykład – język Dycka[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

  • 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 | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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 | edytuj kod]

Przypisy[edytuj | edytuj kod]

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

Bibliografia[edytuj | edytuj kod]