Język kontekstowy
Z Wikipedii
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!).
- – symbol startowy przechodzi w słowo puste lub A
- – w miejsce A generowane jest słowo , gdzie w jest pewnym słowem binarnym, wXR jest zaś tym samym słowem, tyle że odwróconym i przedstawionym w postaci symboli nieterminalnych X0 i X1, zamiast zwykłych 0 i 1
- – znajdujący się najbardziej na lewo symbol słowa XiwXR zostaje zaznaczony
- – zaznaczony symbol wędruje w prawo
- – 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 wXR przejdzie już na prawo, będziemy mieli słowo postaci
- – po wykonaniu całej pracy zmienia się w zwykłe i
Przykładowe wyprowadzenie:
[edytuj] Przykład (2)
Przykładem języka kontekstowego, który nie jest bezkontekstowy jest zbiór słów L = { an : gdzie n jest liczbą pierwszą }