Język kontekstowy

Język kontekstowy (ang. context-sensitive language) – język formalny generowany przez gramatykę kontekstową. W hierarchii Chomskiego 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 \bar{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 ϵ$

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

$A\to 0A{X}_0$

$A\to 1A{X}_1$

$A\to A_0^{*}{X}_0$

$A\to A_1^{*}{X}_1$ – w miejsce $A$ generowane jest słowo $w{A}_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 $w{A}_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 0A{X}_0\to 01A{X}_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ą}