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 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 $A\to \Gamma ,$ gdzie $A$ jest dowolnym symbolem nieterminalnym, i którego znaczenie nie zależy od kontekstu w jakim występuje, a $\Gamma$ 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 $\{a^{n}b^{n}:n\in \mathbb {N} \}$ jest generowany przez:

$S\to aSb,$

$S\to \epsilon .$

Słowo $aaabbb$ możemy wyprowadzić:

$S\to aSb\to aaSbb\to aaaSbbb\to aaabbb.$

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\to \epsilon ,$

$S\to (S),$

$S\to SS.$

Słowo $((())())$ można wyprowadzić:

$S\to (S)\to (SS)\to (S(S))\to ((S)(S))\to (((S))())\to ((())()).$

Ten język nazywa się językiem Dycka. Ogólnie, możemy zdefiniować język Dycka $D_{n}$ dla $n$ możliwych rodzajów nawiasów (tj. nad alfabetem $\{(_{1},)_{1},(_{2},)_{2},\dots ,(_{n},)_{n}\}$) za pomocą gramatyki

$S\to \epsilon$

$S\to (_{1}S)_{1}$

$S\to (_{2}S)_{2}$

$\vdots$

$S\to (_{n}S)_{n}$

$S\to SS$

Własności

Podane poniżej własności mają charakter algorytmiczny, tj. pisząc, że język $X$ jest bezkontekstowy, istnieje stała $n$, istnieje język regularny $R$ 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 $L$ i $L'$ są językami bezkontekstowymi oraz $R$ jest językiem regularnym, to językami bezkontekstowymi są zawsze $L\cup L',$ $LL',$ $L^{*},$ $L^{R},$ $L\cap R.$

• 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ć $A\to BC$ lub $A\to a,$ gdzie $A,B,C$ to symbole nieterminalne, $a$ 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ć $A\to aX,$ gdzie $A$ to symbol nieterminalny, $a$ to symbol terminalny, $X$ to ciąg (być może pusty) symboli nieterminalnych.

• Lemat o pompowaniu: Dla każdego języka bezkontekstowego istnieje takie $n,$ że każde słowo $z$ tego języka długości większej od $n$ można zapisać w postaci $uvwxy,$ gdzie $|vwx|<n,$ przynajmniej jedno z $v$ i $x$ jest niepuste, i dla każdego $k,$ $uv^{k}wx^{k}y$ należy do tego języka.

• Lemat Ogdena: dla każdego języka bezkontekstowego istnieje takie $n,$ że każde słowo $z$ w którym oznaczymy więcej niż $n$ symboli można zapisać w postaci $uvwxy,$ gdzie ilość oznaczonych symboli w $vwx$ jest mniejsza od $n,$ przynajmniej jedno z $v$ i $x$ zawiera oznaczony symbol, i dla każdego $k,$ $uv^{k}wx^{k}y$ 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 $f\colon A^{*}\to \mathbb {N} ^{A}$ przyporządkowuje słowu wektor liczby wystąpień każdej litery w słowie (np. $f(aba)=(2,1)$ dla $A=\{a,b\}$). Wówczas dla każdego języka bezkontekstowego $L\subseteq A^{*}$ istnieje język regularny $R$ taki, że $f(L)=f(R).$ Przykład: dla $L=\{a^{n}b^{n}:n\in \mathbb {N} \}$ można wziąć $R=(ab)^{*}.$

• Twierdzenie Chomsky’ego-Schützenbergera: dla każdego języka bezkontekstowego $L\subseteq A^{*}$ istnieje liczba naturalna $n,$ język regularny $R$ nad alfabetem $A_{n}=\{(_{1},)_{1},\dots ,(_{n},)_{n}\}$ oraz homomorfizm $f\colon A_{n}^{*}\to A^{*}$ taki, że $L=f(D_{n}\cap R)$ ($D_{n}$ 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 $\{a^{n}b^{n}c^{n}:n\in \mathbb {N} \}$ 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 $\{a^{n}b^{m}c^{m}:n,m\in \mathbb {N} \}$ i $\{a^{n}b^{n}c^{m}:n,m\in \mathbb {N} \}.$

Dopełnienie języka bezkontekstowego $\{a^{n}b^{m}c^{k}:n,m,k\in \mathbb {N} ,n\neq m\lor m\neq k\}$ nie jest językiem bezkontekstowym. Gdyby było, to po przecięciu z językiem regularnym $a^{*}b^{*}c^{*}$ dostalibyśmy język bezkontekstowy (tymczasem dostajemy $\{a^{n}b^{n}c^{n}:n\in \mathbb {N} \}$).

Dla każdego $n\geqslant 1$ istnieje język, który można przedstawić jako przecięcie $n+1$ języków bezkontekstowych, ale nie można przedstawić jako przecięcie $n$ 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ć $\{a^{n}b^{n}c^{m}d^{m}:n,m\in \mathbb {N} \}.$

• 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ć $\{a^{n}b^{m}c^{k}:n,m,k\in \mathbb {N} ,n\neq m\lor m\neq k\}.$ (Gdyby był on deterministycznym językiem bezkontekstowym, to jego dopełnienie przecięte z $a^{*}b^{*}c^{*}$ – $\{a^{n}b^{n}c^{n}:n\in \mathbb {N} \}$ 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 $\{a^{n}b^{n}c^{m}d^{m}:n,m\in \mathbb {N} \}\cup \{a^{n}b^{m}c^{m}d^{n}:n,m\in \mathbb {N} \}.$

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 $\Theta (n^{3})$),
• czy istnieje jakiekolwiek słowo, które należy do danego języka,
• czy do danego języka należy co najmniej $n$ 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 $(u_{i},v_{i})$ oznacza $i$-tą parę słów w systemie Posta. Stwórzmy dwa języki bezkontekstowe $L_{1}$ i $L_{2}{:}$

$L_{1}\to u_{i}b_{i},$ dla każdego $i$ odpowiadającego parze słów w systemie Posta,

$L_{1}\to u_{i}L_{1}b_{i},$

$L_{2}\to v_{i}b_{i},$

$L_{2}\to v_{i}L_{2}b_{i},$

gdzie $b_{i}$ są nowymi symbolami terminalnymi, niewystępującymi w żadnym $u_{i}$ ani $v_{i}.$

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

$u_{i_{1}}u_{i_{2}}u_{i_{3}}\cdots u_{i_{n}}b_{i_{n}}\cdots b_{i_{3}}b_{i_{2}}b_{i_{1}}.$

Analogiczną postać mają słowa wygenerowane przez $L_{2}.$ Czyli jeśli istnieje słowo wspólne dla $L_{1}$ i $L_{2},$ 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 $L_{1}$ i $L_{2}$ o rozłącznych nieterminalach, i symbolach startowych odpowiednio $S_{1}$ i $S_{2},$ Zbudujmy następującą gramatykę o symbolu startowym $S{:}$

$S\to S_{1},$

$S\to S_{2},$

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 $S_{1}$ i $S_{2}.$ 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

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.