Ekvivalence (formální jazyky) - Equivalence (formal languages) - Wikipedia

Ve formální jazykové teorii slabá rovnocennost ze dvou gramatiky znamená, že generují stejnou sadu řetězců, tj. že formální jazyk generují je stejný. v teorie překladače pojem se odlišuje od silný (nebo strukturální) rovnocennost, což navíc znamená, že dva analyzovat stromy[je zapotřebí objasnění ] jsou přiměřeně podobné v tom, že oběma lze přiřadit stejnou sémantickou interpretaci.[1]

Vijay-Shanker a Weir (1994)[2] to ukazuje Lineární indexované gramatiky, Kombinované kategoriální gramatiky, Stromové gramatiky, a Vedoucí gramatiky jsou slabě ekvivalentní formalizmy,[je zapotřebí objasnění ] v tom, že všichni definují stejné jazyky řetězců.

Na druhou stranu, pokud dvě gramatiky generují stejnou sadu odvozovacích stromů (nebo obecněji stejnou sadu abstraktních syntaktických objektů), pak jsou tyto dva jazyky silně ekvivalentní. Chomsky (1963)[3] zavádí pojem silné ekvivalence a tvrdí, že při porovnávání gramatických formalizmů je relevantní pouze silná ekvivalence. Kornai a Pullum (1990)[4] a Miller (1994)[5] nabízejí rafinovanou představu silné ekvivalence, která umožňuje izomorfní vztahy mezi syntaktickými analýzami danými různými formalizmy. Yoshinaga, Miyao a Tsujii (2002)[6] nabízí důkaz silné ekvivalence LTAG a HPSG formalizmy.

Bezkontextový příklad gramatiky

Vlevo, odjet: jeden z parsovacích stromů řetězce „1 + 2 * 3“ s první gramatikou. Že jo: jediný analyzovaný strom tohoto řetězce s druhou gramatikou.

Jako příklad zvažte následující dva bezkontextové gramatiky,[poznámka 1] uvedeny v Backus-Naurova forma:

<výraz> ::= <výraz> "+" <výraz> | <výraz> "-" <výraz>               | <výraz> "*" <výraz> | <výraz> "/" <výraz>                | "x" | "y" | "z" | „1“ | "2" | "3" | „(“ <výraz> ")"
<výraz> ::= <období>   | <výraz> "+" <období>   | <výraz> "-" <období><období>       ::= <faktor> |       <období> "*" <faktor> |       <období> "/" <faktor><faktor>     ::= "x" | "y" | "z" | „1“ | "2" | "3" | „(“ <výraz> ")"

Obě gramatiky generují stejnou sadu řetězců, viz. množina všech aritmetických výrazů, které lze sestavit z proměnných „x“, „y“, „z“, konstant „1“, „2“, „3“, operátorů „+“, „-“, „ * "," / "a závorky" ("a") ". Nicméně, a konkrétní syntaxový strom druhé gramatiky vždy odráží obvyklé pořadí operací, zatímco strom z první gramatiky nemusí.

U ukázkového řetězce „1 + 2 * 3“ je v pravé části obrázku zobrazen jedinečný analyzovaný strom s druhou gramatikou;[poznámka 2] hodnotí tento strom ve Windows postfixová objednávka získá správnou hodnotu, 7. Naproti tomu levá obrazová část ukazuje jeden z parsovacích stromů pro tento řetězec s první gramatikou; jeho vyhodnocení v postfixovém pořadí přinese 9.

Jelikož druhá gramatika nemůže generovat strom odpovídající levé obrázkové části, zatímco první gramatika ano, nejsou obě gramatiky silně ekvivalentní.

Generativní kapacita

V lingvistice slabá generativní kapacita a gramatika je definována jako sada všech řetězců, které generuje,[Poznámka 3] zatímco gramatika silná generativní kapacita odkazuje na soubor „strukturálních popisů“[poznámka 4] jím generované.[7]V důsledku toho jsou dvě gramatiky považovány za slabě ekvivalentní, pokud se jejich slabé generativní kapacity shodují; podobné pro silnou rovnocennost. Pojem generativní kapacita byl představen Noam Chomsky v roce 1963.[3][7]

Poznámky

  1. ^ s počáteční symbol „“
  2. ^ pomocí zkratky „E“, „T“ a „F“ pro , a
  3. ^ bezkontextové gramatiky: viz Bezkontextová gramatika # Bezkontextový jazyk pro formální definici
  4. ^ pro bezkontextové gramatiky: konkrétní syntaxové stromy

Reference

  1. ^ Stefano Crespi Reghizzi (2009). Formální jazyky a kompilace. Springer. p. 57. ISBN  978-1-84882-049-4.
  2. ^ Vijay-Shanker, K. a Weir, David J. (1994). „Rovnocennost čtyř rozšíření bezkontextových gramatik“. Teorie matematických systémů. 27 (6): 511–546.CS1 maint: více jmen: seznam autorů (odkaz)
  3. ^ A b Noam Chomsky (1963). Msgstr "Formální vlastnosti gramatiky". V RD Luce; R.R. Bush; E. Galanter (eds.). Příručka matematické psychologie. II. New York: Wiley. str.323 —418.
  4. ^ Kornai, A. a Pullum, G. K. 1990. X-bar Theory of Phrase Structure. Jazyk, 66: 24-50.
  5. ^ Miller, Philip H. 1999. Silná generativní kapacita. Publikace CSLI.
  6. ^ „Yoshinaga, N., Miyao Y. a Tsujii, J. 2002. Formální důkaz silné ekvivalence pro gramatickou konverzi z LTAG do stylu HPSG. Ve sborníku workshopu TAG + 6: 187-192. Benátky, Itálie " (PDF). Archivovány od originál (PDF) dne 28. 8. 2011. Citováno 2012-02-05.
  7. ^ A b Emmon Bach; Philip Miller (2003). "Generativní kapacita" (PDF). V William J. Frawley (ed.). Mezinárodní lingvistická encyklopedie (2. vyd.). Oxford University Press. doi:10.1093 / acref / 9780195139778.001.0001. ISBN  9780195139778.