Sammanhangskänslig grammatik

En kontextkänslig grammatik ( CSG ) är en formell grammatik där de vänstra och högra sidorna av alla produktionsregler kan omges av en kontext av terminala och icke-terminala symboler . Kontextkänsliga grammatiker är mer generella än sammanhangsfria grammatiker , i den meningen att det finns språk som kan beskrivas av en CSG men inte av en kontextfri grammatik. Sammanhangskänsliga grammatiker är mindre generella (i samma mening) än obegränsade grammatiker . Således är CSG:er placerade mellan kontextfria och obegränsade grammatiker i Chomsky-hierarkin .

Ett formellt språk som kan beskrivas med en kontextkänslig grammatik, eller, motsvarande, med en icke-sammandragande grammatik eller en linjärt avgränsad automat , kallas ett sammanhangskänsligt språk . Vissa läroböcker definierar faktiskt CSGs som icke-kontrakterande, även om det inte var så Noam Chomsky definierade dem 1959. Detta val av definition gör ingen skillnad när det gäller de språk som genereras (dvs. de två definitionerna är svagt likvärdiga ), men det gör en skillnad i termer av vilka grammatiker som strukturellt anses kontextkänsliga; den senare frågan analyserades av Chomsky 1963.

Chomsky introducerade kontextkänsliga grammatiker som ett sätt att beskriva syntaxen i naturligt språk där det ofta är så att ett ord kan eller kanske inte är lämpligt på en viss plats beroende på sammanhanget. Walter Savitch har kritiserat terminologin "kontextkänslig" som missvisande och föreslagit "icke-radering" som bättre förklarar skillnaden mellan en CSG och en obegränsad grammatik .

Även om det är välkänt att vissa egenskaper hos språk (t.ex. tvärserieberoende ) inte är kontextfria, är det en öppen fråga hur mycket av CSGs uttryckskraft som behövs för att fånga den kontextkänslighet som finns i naturliga språk. Efterföljande forskning inom detta område har fokuserat på de mer beräkningsmässigt lätthanterliga lätt kontextkänsliga språken . Syntaxerna för vissa visuella programmeringsspråk kan beskrivas med kontextkänsliga grafgrammatiker .

Formell definition

Formell grammatik

Låt oss notera en formell grammatik som G = ( N , Σ, P , S ), med N en uppsättning icke-terminalsymboler, Σ en uppsättning terminalsymboler, P en uppsättning produktionsregler och S ∈ N startsymbolen.

En sträng u ∈ ( N ∪Σ) ^* ger direkt , eller härleder direkt till , en sträng v ∈ ( N ∪Σ) ^* , betecknad som u ⇒ v , om v kan erhållas från u genom en tillämpning av någon produktionsregel i P , det vill säga om $u=\gamma L\delta$ och $v=\gamma R\delta$ , där ${\ displaystyle (L\to R)\in P}$ är en produktionsregel, och $\gamma ,\delta \in (N\cup \Sigma )^{*}$ är den opåverkade vänstra respektive högra delen av strängen. Mer allmänt sägs u ge , eller härleda till , v , betecknad som u ⇒ ^* v , om v kan erhållas från u genom upprepad tillämpning av produktionsregler, det vill säga om u = u ₁ ⇒ ... ⇒ u _n = v för några n ≥0 och några strängar u ₂ , ..., u _{n -1} ∈ ( N ∪Σ) ^* . Med andra ord är relationen (⇒ ^* ) den reflexiva transitiva stängningen av relationen (⇒).

Språket i grammatiken G är mängden av alla terminalsymbolsträngar som kan härledas från dess startsymbol, formellt: L ( G ) = { w ∈ Σ ^* : S ⇒ ^* w }. Härledningar som inte slutar i en sträng som endast består av terminalsymboler är möjliga, men bidrar inte till L ( G ).

Sammanhangskänslig grammatik

En formell grammatik är kontextkänslig om varje regel i P är antingen av formen $S\to \varepsilon$ där $\varepsilon$ är den tomma strängen, eller av formen

α A β → αγβ

med A ∈ N , ${\displaystyle \alpha ,\beta \in (N\cup \Sigma \setminus \{S\})^{*}} ,$ och $\gamma \in (N\cup \Sigma \setminus \{S\})^{+}$ .

Namnet sammanhangskänsligt förklaras av α och β som bildar sammanhanget för A och bestämmer om A kan ersättas med γ eller inte. Detta skiljer sig från en kontextfri grammatik där sammanhanget för en icke-terminal inte tas med i beräkningen. I själva verket är varje produktion av en kontextfri grammatik av formen V → w där V är en enda icke-terminal symbol och w är en sträng av terminaler och/eller icketerminaler; w kan vara tom.

Den enda skillnaden mellan sammanhangskänslig grammatik och obegränsad grammatik är att γ kan vara tom i det obegränsade fallet.

Tillägget av den tomma strängen tillåter påståendet att de sammanhangskänsliga språken är en riktig superset av de sammanhangsfria språken, snarare än att behöva göra det svagare påståendet att alla sammanhangsfria grammatiker utan → ε {\displaystyle \ $varepsilon }$ produktioner är också kontextkänsliga grammatiker.

(Svagt) likvärdiga definitioner

Vissa definitioner av en kontextkänslig grammatik kräver bara att för varje produktionsregel av formen u → v, ska längden på u vara mindre än eller lika med längden på v. Detta till synes svagare krav är i själva verket svagt ekvivalent , se Icke - kontrakterande grammatik#Omvandla till kontextkänslig grammatik . Om möjligheten att lägga till den tomma strängen till ett språk läggs till de strängar som känns igen av de icke-sammandragande grammatikerna (som aldrig kan inkludera den tomma strängen) så är språken i dessa två definitioner identiska.

De vänsterkontext- och högerkontextkänsliga grammatikerna definieras genom att begränsa reglerna till bara formen α A → αγ respektive till bara A β → γβ. Språken som genereras av dessa grammatiker är också hela klassen av sammanhangskänsliga språk. Ekvivalensen fastställdes av Penttonens normalform .

Exempel

a ⁿ b ⁿ c ⁿ

Följande sammanhangskänsliga grammatik, med startsymbolen S , genererar det kanoniska icke -kontextfria språket { a ⁿ b ⁿ c ⁿ : n ≥ 1 } :

1.		S	→	a	B	C
2.		S	→	a	S	B	C
3.	C	B	→	C	Z
4.	C	Z	→	W	Z
5.	W	Z	→	W	C
6.	W	C	→	B	C
7.	a	B	→	a	b
8.	b	B	→	b	b
9.	b	C	→	b	c
10.	c	C	→	c	c

Regel 1 och 2 tillåter sprängning av S till en ⁿ BC ( BC ) ^{n -1} ; reglerna 3 till 6 tillåter successivt utbyte av varje CB till BC ( fyra regler behövs för det eftersom en regel CB → BC inte skulle passa in i schemat α A β → αγβ); reglerna 7–10 tillåter att en icke-terminal B och C ersätts med motsvarande terminaler b respektive c , förutsatt att den är på rätt plats. En generationskedja för aaabbbccc är:

S

→ ₂ aSBC

→ ₂ a aSBC BC

→ ₁ aa aBC BCBC

→ ₃ aaaB CZ CBC

→ ₄ aaaB WZ CBC

→ ₅ aaaB WC CBC

→ ₆ aaaB BC CBC

→ ₃ aaaBBC CZ C

_aaBC → aaaBBC CZ C

→ ₄ _ _ _

_ ₆ aaaBBC BC C

→ ₃ aaaBB CZ CC

→ ₄ aaaBB WZ CC

→ ₅ aaaBB WC CC

→ ₆ aaaBB BC CC

→ ₇ aa ab BBCCC

→ ₈ aaa bb BCCC

→ ₈ aaab bb CCC

→ _bccc → bcc 9

_aa CC _ _ _

_ ₁₀ aaabbbc cc

a ⁿ b ⁿ c ⁿ d ⁿ osv.

Mer komplicerade grammatiker kan användas för att tolka { a ⁿ b ⁿ c ⁿ d ⁿ : n ≥ 1 } och andra språk med ännu fler bokstäver. Här visar vi ett enklare tillvägagångssätt med hjälp av icke-kontrakterande grammatik: Börja med en kärna av vanliga produktioner som genererar meningsformerna $(ABCD)^{n}abcd$ och inkludera sedan de icke upphandlande produktionerna $p_{Da}:Da\rightarrow aD$ , $p_{Db}:Db\rightarrow bD$ , $p_{Dc}:Dc\rightarrow cD$ , $p_{Dd}:Dd\rightarrow dd$ , $p_{Ca}:Ca\rightarrow aC$ , $p_{Cb}:Cb\rightarrow bC$ , $p_{Cc}:Cc\rightarrow cc$ , $p_{Ba}:Ba\rightarrow aB$ , $p_{Bb}:Bb\rightarrow bb$ , $p_{Aa}:Aa\rightarrow aa$ .

a ^m b ⁿ c ^m d ⁿ

En icke sammandragande grammatik (för vilken det finns en motsvarande CSG) för språket ${\displaystyle L_{Cross}=\ {a^{m}b^{n}c^{m}d^{n}:m\geq 1,n\geq 1\}} definieras$ av

$p_{1}:R\rightarrow aRC|aC$ ,

$p_{3}:T\rightarrow BTd|Bd$ ,

$p_{5}:CB\rightarrow BC$ ,

$p_ {0}:S\rightarrow RT$ ,

$p_{6}:aB\rightarrow ab$ ,

$p_{7}:bB\ högerpil bb$ ,

$p_{8}:Cd\rightarrow cd$ , och

$p_{9}:Cc\rightarrow cc$ .

Med dessa definitioner är en härledning för $a^{3}b^{2}c^{3}d^{2}$ : $S\Rightarrow _{p_{0}}RT\Rightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3} T\Rightarrow _{p_{3}p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{ 3}B^{2}C^{3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2} \Rightarrow _{p_{8}p_{9}^{2}}a^{3}b^{2}c^{3}d^{2}$ .

a ^{2 i}

En icke-sammandragande grammatik för språket { a ^{2 i} : i ≥ 1 } konstrueras i exempel 9.5 (s. 224) av (Hopcroft, Ullman, 1979):

1. $S\rightarrow [ACaB]$
2. ${\begin{ fall}\ [Ca]a\högerpil aa[Ca]\\\ [Ca][aB]\högerpil aa[CaB]\\\ [ACa]a\högerpil [Aa]a[Ca]\\\ [ACa] [aB]\högerpil [Aa]a[CaB]\\\ [ACaB]\högerpil [Aa][aCB]\\\ [CaB]\högerpil a[aCB]\end{cases}}$
3. $[aCB]\rightarrow [aDB]$
4. $[aCB]\rightarrow [aE]$
5. ${\begin{cases}\ a[Da]\rightarrow [Da]a\\\ [aDB]\rightarrow [DaB]\\\ [Aa][Da]\högerpil [ADa]a\\\ a[DaB]\högerpil [Da][aB]\\\ [Aa][DaB]\högerpil [ADa][aB] \end{cases}}$
6. $[ADa]\rightarrow [ACa]$
7. ${\begin{cases}\ a[Ea] \rightarrow [Ea]a\\\ [aE]\rightarrow [Ea]\\\ [Aa][Ea]\rightarrow [AEa]a\end{cases}}$
8. $[AEa]\högerpil a$

Kuroda normal form

Varje kontextkänslig grammatik som inte genererar den tomma strängen kan omvandlas till en svagt ekvivalent i Kuroda normalform . "Svagt ekvivalent" betyder här att de två grammatikerna genererar samma språk. Normalformen kommer i allmänhet inte att vara kontextkänslig, utan en icke-sammandragande grammatik .

Kuroda-normalformen är en verklig normalform för icke-sammandragande grammatik.

Egenskaper och användningsområden

Se även: sammanhangskänsligt språk

Ekvivalens med linjärt begränsad automat

Ett formellt språk kan beskrivas med en kontextkänslig grammatik om och bara om det accepteras av någon linjär bunden automat (LBA). I vissa läroböcker tillskrivs detta resultat enbart till Landweber och Kuroda . Andra kallar det Myhill -Landweber-Kuroda-satsen. (Myhill introducerade begreppet deterministisk LBA 1960. Peter S. Landweber publicerade 1963 att språket som accepteras av en deterministisk LBA är kontextkänsligt. Kuroda introducerade begreppet icke-deterministisk LBA och likvärdigheten mellan LBA och CSGs 1964.)

Från och med 2010 är det fortfarande en öppen fråga om varje kontextkänsligt språk kan accepteras av en deterministisk LBA.

Stängningsegenskaper

Kontextkänsliga språk är stängda under komplement . Detta resultat från 1988 är känt som Immerman-Szelepcsényi-satsen . Dessutom är de stängda under union , korsning , sammanlänkning , substitution , omvänd homomorfism och Kleene plus .

Varje rekursivt uppräknat språk L kan skrivas som h ( L ) för något kontextkänsligt språk L och någon stränghomomorfism h .

Beräkningsproblem

Beslutsproblemet som frågar om en viss sträng s tillhör språket för en given kontextkänslig grammatik G , är PSPACE-komplett . Dessutom finns det kontextkänsliga grammatiker vars språk är PSPACE-kompletta. Med andra ord finns det en kontextkänslig grammatik G så att beslutet om en viss sträng s tillhör språket för G är PSPACE-komplett (så G är fixat och endast s är en del av inmatningen av problemet).

Tomhetsproblemet för kontextkänsliga grammatiker (med en kontextkänslig grammatik G , är L ( G )=∅ ?) är obestämbart .

Som modell av naturliga språk

Savitch har bevisat följande teoretiska resultat, på vilket han baserar sin kritik av CSGs som grund för naturligt språk: för varje rekursivt uppräknad uppsättning R , finns det ett kontextkänsligt språk/grammatik G som kan användas som en sorts proxy för att testa medlemskap i R på följande sätt: givet en sträng s , s är i R om och endast om det finns ett positivt heltal n för vilket sc ⁿ är i G, där c är en godtycklig symbol som inte ingår i R .

Det har visat sig att nästan alla naturliga språk i allmänhet kan karaktäriseras av kontextkänsliga grammatiker, men hela klassen av CSG:er verkar vara mycket större än naturliga språk. Ännu värre, eftersom det ovannämnda beslutsproblemet för CSG:er är PSPACE-komplett, vilket gör dem totalt oanvändbara för praktisk användning, eftersom en polynom-tidsalgoritm för ett PSPACE-komplett problem skulle innebära P= NP .

Det bevisades att vissa naturliga språk inte är kontextfria, baserat på att identifiera så kallade cross-serial dependencies och unbounded scrambling- fenomen. Detta betyder dock inte nödvändigtvis att klassen av CSGs är nödvändig för att fånga "kontextkänslighet" i den vardagliga betydelsen av dessa termer i naturliga språk. Till exempel linjära kontextfria omskrivningssystem (LCFRS) strikt svagare än CSG:er men kan förklara fenomenet med tvärseriella beroenden; man kan skriva en LCFRS-grammatik för { a ⁿ b ⁿ c ⁿ d ⁿ | n ≥ 1} till exempel.

Pågående forskning om beräkningslingvistik har fokuserat på att formulera andra klasser av språk som är " milt kontextkänsliga " vars beslutsproblem är genomförbara, såsom trädangränsande grammatiker , kombinatoriska kategorigrammatiker , kopplade sammanhangsfria språk och linjär kontextfri omskrivning system . Språken som genereras av dessa formalismer ligger korrekt mellan de kontextfria och kontextkänsliga språken.

På senare tid har klassen PTIME identifierats med intervallsammansättningsgrammatik , som nu anses vara den mest uttrycksfulla av de milda sammanhangskänsliga språkklasserna.

Se även

• Chomsky hierarki
• Växande kontextkänslig grammatik
• Definitiv sats grammatik#Icke-kontextfria grammatiker
• Lista över parsergeneratorer för sammanhangskänsliga grammatiker

Vidare läsning

•   Meduna, Alexander ; Švec, Martin (2005). Grammatik med kontextvillkor och deras tillämpningar . John Wiley & Sons. ISBN 978-0-471-73655-4 .

externa länkar

• Earley Parsing för kontextkänslig grammatik