Kontextkänsligt språk

Inom formell språkteori är ett sammanhangskänsligt språk ett språk som kan definieras av en kontextkänslig grammatik (och motsvarande av en icke-sammandragande grammatik ). Kontextkänslig är en av de fyra typerna av grammatik i Chomsky-hierarkin .

Beräkningsegenskaper

Beräkningsmässigt är ett sammanhangskänsligt språk ekvivalent med en linjärt avgränsad icke-deterministisk Turing-maskin , även kallad en linjär avgränsad automat . Det är en icke-deterministisk Turing-maskin med ett band av endast $kn$ celler, där $n$ är storleken på inmatningen och $k$ är en konstant associerad med maskinen. Detta betyder att varje formellt språk som kan avgöras av en sådan maskin är ett sammanhangskänsligt språk, och varje kontextkänsligt språk kan avgöras av en sådan maskin.

Denna uppsättning språk är också känd som NLINSPACE eller NSPACE ( O ( n )), eftersom de kan accepteras med linjärt utrymme på en icke-deterministisk Turing-maskin. Klassen LINSPACE (eller DSPACE ( O ( n ))) definieras på samma sätt, förutom att använda en deterministisk Turing-maskin. Uppenbarligen LINSPACE en delmängd av NLINSPACE , men det är inte känt om LINSPACE = NLINSPACE .

Exempel

Ett av de enklaste sammanhangskänsliga men inte sammanhangsfria språken är $L=\{a^{n}b^{n}c^{n} :n\geq 1\}$ : språket för alla strängar som består av $n$ förekomster av symbolen "a", sedan $n$ "b", sedan $n$ "c" (abc, aabbcc, aaabbbccc, etc.) . En superuppsättning av detta språk, kallad Bach-språket, definieras som mängden av alla strängar där "a", "b" och "c" (eller någon annan uppsättning av tre symboler) förekommer lika ofta (aabccb, baabcaccb, etc. ) och är också kontextkänslig.

$L$ kan visas vara ett kontextkänsligt språk genom att konstruera en linjärt begränsad automat som accepterar $L$ . Språket kan enkelt visas som varken regelbundet eller kontextfritt genom att applicera respektive pumpande lemman för var och en av språkklasserna på $L$ .

Liknande:

$L_{Cross}=\{a^{m}b^{n}c^{m} d^{n}:m\geq 1,n\geq 1\}$ är ett annat sammanhangskänsligt språk; motsvarande sammanhangskänsliga grammatik kan enkelt projiceras med början med två sammanhangsfria grammatiker som genererar meningsformer i formaten $a^{m}C^{m}$ och $B ^{n}d^{n}$ och sedan komplettera dem med en permutationsproduktion som $CB\rightarrow BC$ , en ny startsymbol och standardsyntaktisk socker.

$L_{MUL3}=\{a^{m}b^{n}c^{mn}:m \geq 1,n\geq 1\}$ är ett annat sammanhangskänsligt språk ("3" i namnet på detta språk är avsett att betyda ett ternärt alfabet); det vill säga, operationen "produkt" definierar ett sammanhangskänsligt språk (men "summan" definierar endast ett sammanhangsfritt språk som grammatiken $S\rightarrow aSc|R$ och $R\rightarrow bRc|bc$ visas). På grund av produktens kommutativa egenskap är den mest intuitiva grammatiken för $L_{MUL3}$ tvetydig. Detta problem kan undvikas med tanke på en på något sätt mer restriktiv definition av språket, t.ex. $L_{ORDMUL3}=\{ a^{m}b^{n}c^{mn}:1<m<n\}$ . Detta kan specialiseras till $L_{MUL1}=\{a^{mn}:m>1,n>1\}$ och från detta till $L_{m^{2}}=\{a^{m^{2}}:m>1\}$ , ${\displaystyle L_{m^{3}}=\{a^{m^{3}}:m>1\}},$ etc.

$L_{REP}=\{w^{|w|}:w\in \Sigma ^{*}\}$ är ett sammanhangskänsligt språk. Motsvarande sammanhangskänsliga grammatik kan erhållas som en generalisering av de sammanhangskänsliga grammatikerna för $L_{Square}=\{w^{2 }:w\in \Sigma ^{*}\}$ , $L_{Cube}=\{w^{3}:w\in \ Sigma ^{*}\}$ osv.

$L_{EXP}=\{a^{2^{n}}:n\geq 1\}$ är ett sammanhangskänsligt språk.

$L_{PRIMES2}=\{w:|w|{\mbox{ är prime }}\}$ är ett sammanhangskänsligt språk ("2" i namnet på detta språk är avsett att betyda ett binärt alfabet). Detta bevisades genom att Hartmanis använde pumpande lemman för vanliga och kontextfria språk över ett binärt alfabet och, efter det, skissade en linjärt avgränsad multitapeautomat som accepterar $L_{PRIMES2}$ .

$L_{PRIMES1}=\{a^{p}:p{\mbox{ är primtal }}\}$ är en kontextkänslig språk ("1:an" i namnet på detta språk är avsett att betyda ett unärt alfabet). Detta krediterades av A. Salomaa till Matti Soittola med hjälp av en linjärt avgränsad automat över ett unärt alfabet (sidorna 213-214, övning 6.8) och även till Marti Penttonen med hjälp av en kontextkänslig grammatik även över ett enaralfabet (se : Formella språk av A. Salomaa, sidan 14, exempel 2.5).

Ett exempel på rekursivt språk som inte är kontextkänsligt är vilket rekursivt språk som helst vars beslut är ett EXPSPACE -hårt problem, säg uppsättningen av par av ekvivalenta reguljära uttryck med exponentiering.

Egenskaper för sammanhangskänsliga språk

Föreningen, skärningspunkten, sammanlänkningen av två kontextkänsliga språk är kontextkänslig, även Kleene plus för ett kontextkänsligt språk är kontextkänsligt.
Komplementet av ett sammanhangskänsligt språk är i sig sammanhangskänsligt, ett resultat som kallas Immerman-Szelepcsényi-satsen .
Medlemskap av en sträng på ett språk som definieras av en godtycklig kontextkänslig grammatik, eller av en godtycklig deterministisk kontextkänslig grammatik, är ett PSPACE-komplett problem.

Se även

Linjärt avgränsad automat
Lista över parsergeneratorer för sammanhangskänsliga språk
Chomsky hierarki
Indexerade språk – en strikt delmängd av de sammanhangskänsliga språken
Weir hierarki

Sipser, M. (1996), Introduction to the Theory of Computation , PWS Publishing Co.