Kontekstno ovisna gramatika

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

αAβ → αγβ

pri čemu je A ∈ N (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.

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.

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 ${\displaystyle \{a^{n}b^{n}c^{n}:n\geq 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 ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}:n\geq 1\}}$  , ali je mnogo složenija od gramatike predstavljene gore.

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.

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.

• Siniša Srbljić (2003). Jezični procesori 1. Element. ISBN 953-197-129-3.