Język kontekstowy

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Język kontekstowy (ang. context-sensitive language) to język formalny taki, że rozstrzygnąć czy dany łańcuch należy do języka może algorytm niedeterministyczny w przestrzeni liniowej. Języki kontekstowe opisuje się za pomocą gramatyk kontekstowych.

Wszystkie języki bezkontekstowe są kontekstowe. Wszystkie języki kontekstowe są rekursywne.

[edytuj] Przykład

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

$S \rightarrow \epsilon$

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

A

$A \rightarrow 0AX_0$

$A \rightarrow 1AX_1$

$A \rightarrow A_0^*X_0$

$A \rightarrow A_1^*X_1$ – w miejsce

A

generowane jest słowo $wA_i^*X_iw^{XR}$ , gdzie

w

jest pewnym słowem binarnym,

w X R

jest zaś tym samym słowem, tyle że odwróconym i przedstawionym w postaci symboli nieterminalnych

X 0

X 1

, zamiast zwykłych 0 i 1

$A_0^*X_0 \rightarrow A_0^*X_0^*$

$A_0^*X_1 \rightarrow A_0^*X_1^*$

$A_1^*X_0 \rightarrow A_1^*X_0^*$

$A_1^*X_1 \rightarrow A_1^*X_1^*$ – znajdujący się najbardziej na lewo symbol słowa

X i w X R

zostaje zaznaczony

$X_0^*X_0 \rightarrow X_0X_0^*$

$X_0^*X_1 \rightarrow X_1X_0^*$

$X_1^*X_0 \rightarrow X_0X_1^*$

$X_1^*X_1 \rightarrow X_1X_1^*$ – zaznaczony symbol wędruje w prawo

$X_0^* \rightarrow 0$

$X_1^* \rightarrow 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 X R

przejdzie już na prawo, będziemy mieli słowo postaci $wA_i^*wi$

$A_0^* \rightarrow 0$

$A_1^* \rightarrow 1$ – $A_i^*$ po wykonaniu całej pracy zmienia się w zwykłe

i

Przykładowe wyprowadzenie:

$S \rightarrow A \rightarrow 0AX_0 \rightarrow 01AX_1X_0 \rightarrow 01A_1^*X_1X_1X_0 \rightarrow 01A_1^*X_1^*X_1X_0$

$01A_1^*X_1^*X_1X_0 \rightarrow 01A_1^*X_1X_1^*X_0 \rightarrow 01A_1^*X_1X_0X_1^* \rightarrow 01A_1^*X_1X_01$

$01A_1^*X_1X_01 \rightarrow 01A_1^*X_1^*X_01 \rightarrow 01A_1^*X_0X_1^*1 \rightarrow 01A_1^*X_011 \rightarrow 01A_1^*X_0^*11 \rightarrow 01A_1^*011 \rightarrow 011011$