koncept v generalizovaném kontextu bezplatná gramatika
Hlava gramatiky (HG) je gramatický formalizmus zavedený v Carl Pollard (1984)[1] jako rozšíření bezkontextová gramatika třída gramatik. Hlavová gramatika je tedy typem frázová struktura gramatiky, na rozdíl od a závislost gramatiky. Třída hlavových gramatik je podmnožinou lineární bezkontextové přepisovací systémy.
Jedním z typických způsobů definování gramatik hlavy je nahrazení koncových řetězců CFG indexovanými koncovými řetězci, kde index označuje slovo „head“ řetězce. Tedy například pravidlo CF, jako je místo toho může být , kde je 0. terminál, A, je hlava výsledného terminálového řetězce. Pro usnadnění zápisu lze takové pravidlo zapsat pouze jako řetězec terminálu, přičemž hlavní terminál je označen nějakou značkou, jako v .
Ke všem pravidlům přepisování jsou poté přidány dvě základní operace: zalamování a zřetězení.
Operace na hlavičkových strunách
Obal
Obtékání je operace na dvou hlavičkových řetězcích definovaných takto:
Nechat a být koncové řetězce v čele s X a y, resp.
Zřetězení
Zřetězení je rodina operací na n> 0 hlavičkových řetězcích, definovaných pro n = 1, 2, 3 takto:
Nechat , , a být koncové řetězce v čele s X, y, a z, resp.
A tak dále . Lze zde shrnout vzor jednoduše jako „zřetězit určitý počet koncových řetězců m, s hlavou struny n označen jako hlava výsledného řetězce ".
Forma pravidel
Pravidla gramatiky hlavy jsou definována z hlediska těchto dvou operací, přičemž pravidla mají jednu z forem
kde , , ... jsou každý buď terminální řetězec, nebo neterminální symbol.
Příklad
Gramatiky hlavy jsou schopné generovat jazyk . Můžeme definovat gramatiku takto:
Odvození slova „abcd“ je tedy:
A pro „aabbccdd“:
Formální vlastnosti
Rovnocennost
Vijay-Shanker a Weir (1994)[2] prokázat to lineární indexované gramatiky, kombinační kategoriální gramatika, stromové gramatiky a hlavové gramatiky jsou slabě ekvivalentní formalizmy, protože všechny definují stejné řetězce jazyků.
Reference
- ^ Pollard, C. 1984. Zobecněné frázové strukturní gramatiky, gramatiky hlavy a přirozený jazyk. Ph.D. práce, Stanford University, CA.
- ^ Vijay-Shanker, K. a Weir, David J. 1994. Ekvivalence čtyř rozšíření bezkontextových gramatik. Teorie matematických systémů 27 (6): 511-546.
|
---|
|
Každá kategorie jazyků, kromě těch, které jsou označeny a *, je správná podmnožina kategorie přímo nad ní. Libovolný jazyk v každé kategorii je generován gramatikou a automatem v kategorii na stejném řádku. |