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.
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 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:
![{\displaystyle S\to \epsilon ,}](//wikimedia.org/api/rest_v1/media/math/render/svg/70c88f76594f265836c95efc0eab81a38894c2fb)
![{\displaystyle S\to (S),}](//wikimedia.org/api/rest_v1/media/math/render/svg/5113d33d4891e3688e0e2142e40e269a29c11767)
![{\displaystyle S\to SS.}](//wikimedia.org/api/rest_v1/media/math/render/svg/8429649ce520202b234b8f25483c81893ff931ba)
Słowo
można wyprowadzić:
![{\displaystyle S\to (S)\to (SS)\to (S(S))\to ((S)(S))\to (((S))())\to ((())()).}](//wikimedia.org/api/rest_v1/media/math/render/svg/497f9aae45e6ff535b6f653e7f2ac521fe5917aa)
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
![{\displaystyle S\to \epsilon }](//wikimedia.org/api/rest_v1/media/math/render/svg/18fa67d66e9d16110ee795b632d399eec6855320)
![{\displaystyle S\to (_{1}S)_{1}}](//wikimedia.org/api/rest_v1/media/math/render/svg/318cc52d1427563130bee962cefb9a95e4e430c1)
![{\displaystyle S\to (_{2}S)_{2}}](//wikimedia.org/api/rest_v1/media/math/render/svg/513030b27bed9873a7c76ec2ae33852d6ee902d1)
![{\displaystyle \vdots }](//wikimedia.org/api/rest_v1/media/math/render/svg/f8039d9feb6596ae092e5305108722975060c083)
![{\displaystyle S\to (_{n}S)_{n}}](//wikimedia.org/api/rest_v1/media/math/render/svg/7978fddaf89443dbca36018e82553f7ebac86d25)
![{\displaystyle S\to SS}](//wikimedia.org/api/rest_v1/media/math/render/svg/4ae251f20cc301f774400ea3482b018a785ed02d)
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
![{\displaystyle L\cap R.}](//wikimedia.org/api/rest_v1/media/math/render/svg/09cd3660f50dac2ba8b4216ebaed3d37c3f0374f)
- 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ąć ![{\displaystyle R=(ab)^{*}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/ba53ba8855f447f125cc9046fa1bf8a6f45bb56b)
- 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
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 ![{\displaystyle \{a^{n}b^{n}c^{m}:n,m\in \mathbb {N} \}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/4f7b55d1c38b04689646e60ab07873de208652ab)
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].
- 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ć
![{\displaystyle \{a^{n}b^{n}c^{m}d^{m}:n,m\in \mathbb {N} \}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/bc94121d5e66bf4597e4fb7c40781635b81d1d9a)
- 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
![{\displaystyle \{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} \}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/7ae8c7013f1a710527f5392bd4dc6689d8565750)
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 ![{\displaystyle L_{2}{:}}](//wikimedia.org/api/rest_v1/media/math/render/svg/360bb86064acd5b3daaea2e783351c9a674e9929)
dla każdego
odpowiadającego parze słów w systemie Posta,
![{\displaystyle L_{1}\to u_{i}L_{1}b_{i},}](//wikimedia.org/api/rest_v1/media/math/render/svg/957ef328b02542e6f16203a6715aa96d8daeee46)
![{\displaystyle L_{2}\to v_{i}b_{i},}](//wikimedia.org/api/rest_v1/media/math/render/svg/c97437c9940dc0f5fa741e32a3476dee0e0b2b41)
![{\displaystyle L_{2}\to v_{i}L_{2}b_{i},}](//wikimedia.org/api/rest_v1/media/math/render/svg/50a92a820fa6d849cfa9a6c658b3638e16cd0791)
gdzie
są nowymi symbolami terminalnymi, niewystępującymi w żadnym
ani ![{\displaystyle v_{i}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/e5f6b09bb5d4cc2995af950d87d91ad372e9c085)
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:
![{\displaystyle 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}}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/b4a8f33e3ab1f9d4b7c8e30ab26fa20f598f1cca)
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.