Język kontekstowy

Język kontekstowy (ang. context-sensitive language) – język formalny generowany przez gramatykę kontekstową. W hierarchii Chomsky’ego jest zdefiniowany jako język typu 1. Klasa języków kontekstowych jest właściwym podzbiorem klasy języków rekurencyjnych.

Definicje

Istnieje kilka równoważnych definicji języka kontekstowego. Język L nazywamy kontekstowym wtedy i tylko wtedy, gdy:

1. Istnieje gramatyka kontekstowa G generująca język L.
2. Istnieje automat liniowo ograniczony potrafiący rozstrzygnąć czy słowo x należy do języka L.

Językami kontekstowymi są wszystkie języki bezkontekstowe oraz języki regularne.

Właściwości

Klasa języków kontekstowych $L_{K}$ jest zamknięta ze względu na operacje:

1. sumy teoriomnogościowej: $L_{1},L_{2}\in L_{K}\Rightarrow L_{1}\cup L_{2}\in L_{K}$
2. iloczynu teoriomnogościowego: $L_{1},L_{2}\in L_{K}\Rightarrow L_{1}\cap L_{2}\in L_{K}$
3. konkatenację: $L_{1},L_{2}\in L_{K}\Rightarrow L_{1}L_{2}\in L_{K}$
4. dopełnienie: $L\in L_{K}\Rightarrow {\overline {L}}\in L_{K}$

Rozstrzygnięcie, czy słowo x należy do języka kontekstowego L, jest problemem PSPACE-zupełnym.

Przykład

Język słów nad alfabetem binarnym, których pierwsza połowa równa jest drugiej, jest kontekstowy (ale nie bezkontekstowy!).

$S\to \epsilon$

$S\to A$ – symbol startowy przechodzi w słowo puste lub $A$

$A\to 0AX_{0}$

$A\to 1AX_{1}$

$A\to A_{0}^{*}X_{0}$

$A\to A_{1}^{*}X_{1}$ – w miejsce $A$ generowane jest słowo $wA_{i}^{*}X_{i}w^{XR},$ gdzie $w$ jest pewnym słowem binarnym, $w^{XR}$ jest zaś tym samym słowem, tyle że odwróconym i przedstawionym w postaci symboli nieterminalnych $X_{0}$ i $X_{1},$ zamiast zwykłych 0 i 1

$A_{0}^{*}X_{0}\to A_{0}^{*}X_{0}^{*}$

$A_{0}^{*}X_{1}\to A_{0}^{*}X_{1}^{*}$

$A_{1}^{*}X_{0}\to A_{1}^{*}X_{0}^{*}$

$A_{1}^{*}X_{1}\to A_{1}^{*}X_{1}^{*}$ – znajdujący się najbardziej na lewo symbol słowa $X_{i}w^{XR}$ zostaje zaznaczony

$X_{0}^{*}X_{0}\to X_{0}X_{0}^{*}$

$X_{0}^{*}X_{1}\to X_{1}X_{0}^{*}$

$X_{1}^{*}X_{0}\to X_{0}X_{1}^{*}$

$X_{1}^{*}X_{1}\to X_{1}X_{1}^{*}$ – zaznaczony symbol wędruje w prawo

$X_{0}^{*}\to 0$

$X_{1}^{*}\to 1$ – i na końcu zmienia się w symbol terminalny, któremu odpowiada. Pozwalamy co prawda $X$-owi zmienić się szybciej, ale wtedy żaden z $X$-ów na prawo od niego nigdy nie zamieni się w symbol terminalny, więc reguła ta de facto może być użyta tylko kiedy nie ma już żadnych nieterminali na prawo od zmienianego. Kiedy całe słowo $w^{XR}$ przejdzie już na prawo, będziemy mieli słowo postaci $wA_{i}^{*}wi$

$A_{0}^{*}\to 0$

$A_{1}^{*}\to 1$ – $A_{i}^{*}$ po wykonaniu całej pracy zmienia się w zwykłe $i$

Przykładowe wyprowadzenie:

$S\to A\to 0AX_{0}\to 01AX_{1}X_{0}\to 01A_{1}^{*}X_{1}X_{1}X_{0}\to 01A_{1}^{*}X_{1}^{*}X_{1}X_{0}$

$01A_{1}^{*}X_{1}^{*}X_{1}X_{0}\to 01A_{1}^{*}X_{1}X_{1}^{*}X_{0}\to 01A_{1}^{*}X_{1}X_{0}X_{1}^{*}\to 01A_{1}^{*}X_{1}X_{0}1$

$01A_{1}^{*}X_{1}X_{0}1\to 01A_{1}^{*}X_{1}^{*}X_{0}1\to 01A_{1}^{*}X_{0}X_{1}^{*}1\to 01A_{1}^{*}X_{0}11\to 01A_{1}^{*}X_{0}^{*}11\to 01A_{1}^{*}011\to 011011$

Przykład (2)

Przykładem języka kontekstowego, który nie jest bezkontekstowy jest zbiór słów L = {$a^{n}{:}$ gdzie n jest liczbą pierwszą}