Ekvivalens (formella språk)

I formell språkteori betyder svag likvärdighet mellan två grammatiker att de genererar samma uppsättning strängar, dvs att det formella språket de genererar är detsamma. I kompilatorteorin skiljs begreppet från stark (eller strukturell ) ekvivalens , vilket dessutom betyder att de två parse-träden är rimligt lika i det att samma semantiska tolkning kan tilldelas båda.

Weir (1994) visar att linjära indexerade grammatiker , kombinationskategorier , trädangränsande grammatiker och huvudgrammatik är svagt likvärdiga formalismer, ] genom att de alla definierar samma strängspråk.

Å andra sidan, om två grammatiker genererar samma uppsättning härledningsträd (eller mer allmänt, samma uppsättning abstrakta syntaktiska objekt), så är de två grammatikerna starkt ekvivalenta. Chomsky (1963) introducerar begreppet stark ekvivalens och hävdar att endast stark ekvivalens är relevant när man jämför grammatikformalismer. Kornai och Pullum (1990) och Miller (1994) erbjuder en förfinad föreställning om stark ekvivalens som möjliggör isomorfa relationer mellan de syntaktiska analyser som ges av olika formalism. Yoshinaga, Miyao och Tsujii (2002) ger ett bevis på att HPSG- formalism för varje LTAG -formalism .

Exempel på kontextfri grammatik

Vänster: ett av analysträden för strängen "1+2*3" med den första grammatiken. Höger: det enda analysträdet i den strängen med den andra grammatiken.

Som ett exempel, betrakta följande två sammanhangsfria grammatiker , givna i Backus-Naur-form :

   <  uttryck  >  ::=  <  uttryck  >  "+"  <  uttryck  >  |  <  uttryck  >  "-"  <  uttryck  >  |  <  uttryck  >  "*"  <  uttryck  >  |  <  uttryck  >  "/"  <  uttryck  >  | "x" |  "y" |  "z" |  "1" |  "2" |  "3" |  "("   <  uttryck  >  ")" 

  
        
      <  uttryck  >  ::=  <  term  >  |  <  uttryck  >  "+"  <  term  >  |  <  uttryck  >  "-"  <  term  >  <  term  >  ::=  <  faktor  >  |  <  term  >  "*"  <  faktor  >  |  <  term  >  "/"  <  faktor  >  <  faktor  >  ::=  "x" | "y" |  "z" |  "1" |  "2" |  "3" |  "("   <  uttryck  >  ")" 

Båda grammatikerna genererar samma uppsättning strängar, dvs. mängden av alla aritmetiska uttryck som kan byggas från variablerna "x", "y", "z", konstanterna "1", "2", "3", operatorerna "+", "-", " *", "/", och parenteser "(" och ")". Ett konkret syntaxträd för den andra grammatiken återspeglar dock alltid den vanliga operationsordningen , medan ett träd från den första grammatiken inte behöver.

För exempelsträngen "1+2*3" visar den högra delen av bilden dess unika analysträd med den andra grammatiken; att utvärdera detta träd i postfix-ordning kommer att ge rätt värde, 7. Däremot visar den vänstra bilddelen ett av analysträden för den strängen med den första grammatiken; att utvärdera det i postfix-ordning kommer att ge 9.

Eftersom den andra grammatiken inte kan generera ett träd som motsvarar den vänstra bilddelen, medan den första grammatiken kan, är båda grammatikerna inte starkt ekvivalenta.

Generativ kapacitet

Inom lingvistik definieras den svaga generativa kapaciteten hos en grammatik som mängden av alla strängar som genereras av den, medan en grammatiks starka generativa kapacitet hänvisar till den uppsättning "strukturella beskrivningar" som genereras av den. Som en konsekvens anses två grammatiker vara svagt ekvivalenta om deras svaga generativa kapacitet sammanfaller; liknande för stark ekvivalens. Begreppet generativ kapacitet introducerades av Noam Chomsky 1963.