Język kontekstowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Język kontekstowy (ang. context-sensitive language) to 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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^{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 \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_iw^{XR} 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^{XR} przejdzie już na prawo, będziemy mieli słowo postaci wA_i^*wi
A_0^* \rightarrow 0
A_1^* \rightarrow 1A_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

Przykład (2)[edytuj | edytuj kod]

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

Przypisy

  1. 1,0 1,1 Maria Foryś, Wit Foryś, Adam Roman: Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga (pol.). W: Języki, automaty i obliczenia – wazniak.mimuw.edu.pl [on-line]. [dostęp 29 września 2009].
  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 29 września 2009]. [zarchiwizowane z tego adresu (2006-06-22)].