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 jest zamknięta ze względu na operacje:

  1. sumy teoriomnogościowej:
  2. iloczynu teoriomnogościowego:
  3. konkatenację:
  4. dopełnienie:

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!).

– symbol startowy przechodzi w słowo puste lub
– w miejsce generowane jest słowo gdzie jest pewnym słowem binarnym, jest zaś tym samym słowem, tyle że odwróconym i przedstawionym w postaci symboli nieterminalnych i zamiast zwykłych 0 i 1
– znajdujący się najbardziej na lewo symbol słowa zostaje zaznaczony
– zaznaczony symbol wędruje w prawo
– i na końcu zmienia się w symbol terminalny, któremu odpowiada. Pozwalamy co prawda -owi zmienić się szybciej, ale wtedy żaden z -ó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 przejdzie już na prawo, będziemy mieli słowo postaci
po wykonaniu całej pracy zmienia się w zwykłe

Przykładowe wyprowadzenie:

Przykład (2)

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

Przypisy

  1. a b 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)].