Kontekstno ovisna gramatika

Izvor: Wikipedija
Skoči na: orijentacija, traži

Kontekstno ovisna gramatika (rjeđe još i gramatika ovisna o sadržaju, te okolinska gramatika, kontekstualna gramatika[1]) je formalna gramatika u kojoj lijeve i desne strane bilo koje produkcije mogu biti okružene kontekstom završnih i nezavršnih znakova. Kontekstno ovisne gramatike su općenitije od kontekstno neovisnih gramatika, ali još uvijek dovoljno pravilne da mogu biti parsirane linearno ograničenim automatom.

Koncept kontekstno ovisne gramatike je uveo Noam Chomsky 1950-ih kao sredstvo opisa sintakse prirodnog jezika u kojem je zaista čest slučaj da riječ može ali i ne mora biti prikladna na određenim mjestima ovisno o kontekstu. Formalni jezik koji kontekstno ovisna gramatika opisuje se zove kontekstno ovisni jezik.

Formalna definicija[uredi VE | uredi]

Formalna gramatika G = (N, Σ, P, S) je kontekstno ovisna ako sve produkcije u P imaju oblik

αAβ → αγβ

pri čemu je AN (tj. A je jedan nezavršni znak), α,β ∈ (N U Σ)* (tj. α i β su nizovi nezavršnih i završnih znakova) te γ ∈ (N U Σ)+ (tj. γ je neprazni niz završnih i nezavršnih znakova). Kao dodatak, produkcija oblika

S → ε

pri čemu ε predstavlja prazni niz je dozvoljena ako se S ne pojavljuje na desnoj strani neke od produkcija iz P.

Ime kontekstno ovisna se objašnjava nizovima znakova α i β koji oblikuju kontekst znaka A i time određuju može li se A zamijeniti sa γ ili ne. Ovo je različito od kontekstno neovisne gramatike koje ne uzima u obzir kontekst nezavršnog znaka.

Alternativna definicija[uredi VE | uredi]

Druga definicija kontekstno ovisnih gramatika ih definira kao formalne gramatike sa ograničenjem da za sva pravila α -> β u P vrijedi |α| ≤ |β| pri čemu je |α| duljina niza znakova α. Takva gramatika se još zove i monotona ili nekontraktirajuća gramatika pošto nijedna od njenih produkcija ne smanjuje duljinu prepisanog niza znakova.

Iako su nekontraktirajuće gramatike drugačije od kontekstno ovisnih, one su gotovo istovjetne u smislu definiranja iste klase jezika (osim što nekontraktirajuće gramatike ne mogu generirati jezik koji sadrži prazni niz ε). Ali ako se formalni jezik L može opisati gramatikom danom prvom definicijom, tada postoji nekontraktirajuća gramatika koja opisuje L - {ε}, a vrijedi i obrat ove tvrdnje.

Primjer[uredi VE | uredi]

Jednostavna monotona gramatika (koja nije kontekstno ovisna po prvoj definiciji) jest

S → abc | aSBc
cB → Bc
bB → bb

pri čemu se specijalni znak | koristi za razdvajanje različitih opcija za isti nezavršni znak. Ova gramatika generira jezik  \{ a^n b^n c^n : n \ge 1 \} , koji nije kontekstno neovisan. Kontekstno ovisne gramatike mogu odraditi uparivanje (balansiranje) neograničenog broja znakova i njihovih partnera, za razliku od kontekstno neovisnih gramatika, koje mogu odraditi uparivanje samo jednog znaka i njegova partnera, pa tako postoji i kontekstno ovisna gramatika za jezik  \{ a^n b^n c^n d^n : n \ge 1 \} , ali je mnogo složenija od gramatike predstavljene gore.

Normalne forme[uredi VE | uredi]

Svaka se kontekstno ovisna gramatika koja ne generira prazni niz može preoblikovati u istovjetnu gramatiku u Kurodinom normalnom obliku. "Istovjetan" ovdje označava da gramatike generiraju isti jezik.

Računska svojstva i uporabe[uredi VE | uredi]

Problem odluke koji određuje pripada li određeni niz s jeziku određene kontekstno ovisne gramatike G je PSPACE-potpun. Postoje čak i neke kontekstno ovisne gramatike čiji je fiksni problem prepoznavanja gramatike PSPACE-potpun.

Pokazano je da se gotovo svi prirodni jezici mogu općenito opisati kontekstno ovisnim gramatikama, iako međutim izgleda da je cijela klasa kontekstno ovisnih gramatika mnogo veća od klase prirodnih jezika. Još je gora posljedica već spomenute činjenice da jer problem odluke za kontekstno ovisne gramatike PSPACE-potpun, ta da ih to čini potpuno nepraktičnim za uporabu, pošto bi općeniti algoritam zahtijevao eksponencijalno vrijeme. Trenutni istraživački rad u području računalne lingvisitke je fokusiran na formuliranje klasa jezika koje su "umjereno kontekstno ovisne" i čiji su problemi odluke praktično izvodljivi, poput npr. tree-adjoining gramatike, coupled kontekstno slobodnih jezika i tzv. linear context-free rewriting systems. Jezici koje ovi formalizmi generiraju leže između kontekstno neovisnih i kontekstno ovisnih jezika.

Izvori[uredi VE | uredi]

  1. Kiš Miroslav, Englesko-hrvatski i hrvatsko-engleski informatički rječnik, Zagreb, Naklada Ljevak, 2000., str. 234
Teorija automata: formalni jezici i formalne gramatike
Chomskyjeva
hijerarhija
Gramatike Jezici Minimalni
automat
Tip 0 Neograničenih produkcija Rekurzivno prebrojiv Turingov stroj
n/a (nema uobičajenog imena) Rekurzivni Odlučitelj
Tip 1 Kontekstno ovisna Kontekstno ovisni Linearno ograničen
n/a Indeksirana Indeksirani Ugniježđenog stoga
Tip 2 Kontekstno neovisna Kontekstno neovisni Nedeterministički potisni
n/a Deterministička kontekstno neovisna Deterministički kontekstno neovisni Deterministički potisni
Tip 3 Regularna Regularni Konačni
Svaka kategorija jezika ili gramatika je pravi podskup nadređene kategorije.