Język kontekstowy

Język kontekstowy (ang. context-sensitive language) – język formalny generowany przez gramatykę kontekstową^[1]. 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^[1].
2. Istnieje automat liniowo ograniczony potrafiący rozstrzygnąć czy słowo x należy do języka L^[2].

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

Właściwości

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

1. sumy teoriomnogościowej: ${\displaystyle L_{1},L_{2}\in L_{K}\Rightarrow L_{1}\cup L_{2}\in L_{K}}$
2. iloczynu teoriomnogościowego: ${\displaystyle L_{1},L_{2}\in L_{K}\Rightarrow L_{1}\cap L_{2}\in L_{K}}$
3. konkatenację: ${\displaystyle L_{1},L_{2}\in L_{K}\Rightarrow L_{1}L_{2}\in L_{K}}$
4. dopełnienie: ${\displaystyle 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!).

${\displaystyle S\to \epsilon }$

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

${\displaystyle A\to 0AX_{0}}$

${\displaystyle A\to 1AX_{1}}$

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle X_{1}^{*}\to 1}$ – i na końcu zmienia się w symbol terminalny, któremu odpowiada. Pozwalamy co prawda ${\displaystyle X}$-owi zmienić się szybciej, ale wtedy żaden z ${\displaystyle 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 ${\displaystyle w^{XR}}$ przejdzie już na prawo, będziemy mieli słowo postaci ${\displaystyle wA_{i}^{*}wi}$

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

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

Przykładowe wyprowadzenie:

${\displaystyle 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}}$

${\displaystyle 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}$

${\displaystyle 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 = {${\displaystyle a^{n}{:}}$ gdzie n jest liczbą pierwszą}

Przypisy

1. Maria Foryś, Wit Foryś, Adam Roman: Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga. [w:] Języki, automaty i obliczenia – wazniak.mimuw.edu.pl [on-line]. [dostęp 2009-09-29]. (pol.).
2. dr inż. Janusz Majewski: Automat liniowo ograniczony. [w:] Materiały wykładowe dla studentów informatyki AGH – teoria automatów i języków formalnych [on-line]. 2009-03-07. [dostęp 2009-09-29]. [zarchiwizowane z tego adresu (2006-06-22)].