Język bezkontekstowy

Język bezkontekstowy (Szablon:Ang.) – 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 $A\to \mathrm{\Gamma },$ gdzie $A$ jest dowolnym symbolem nieterminalnym, i którego znaczenie nie zależy od kontekstu w jakim występuje, a $\mathrm{\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 ϵ.$

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 ϵ,$

$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 ϵ$

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

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

$⋮$

$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^{\prime }$ są językami bezkontekstowymi oraz $R$ jest językiem regularnym, to językami bezkontekstowymi są zawsze $L\cup L^{\prime },$ $L{L}^{\prime },$ $L^{*},$ $L^R,$ $L\cap R.$

• 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ć $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,$ $u{v}^{k}w{x}^{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,$ $u{v}^{k}w{x}^{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: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 Chomskiego-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: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\ne m\vee m\ne 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⩾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\ne m\vee m\ne 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 $\mathrm{\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

• Szablon:Cytuj książkę