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.

DefinicjeEdytuj

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ściEdytuj

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ładEdytuj

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)Edytuj

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

PrzypisyEdytuj

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