Zobecněná bezkontextová gramatika - Generalized context-free grammar

Zobecněná bezkontextová gramatika (GCFG) je gramatický formalizmus, který se rozšiřuje bezkontextové gramatiky přidáním potenciálně bezkontextových funkcí kompozice k přepsání pravidel.^[1] Hlava gramatiky (a jeho slabé ekvivalenty) je příkladem takového GCFG, o kterém je známo, že je obzvláště zběhlý v manipulaci s celou řadou přirozených jazyků bez CF vlastností.

Popis

GCFG se skládá ze dvou komponent: sady funkcí kompozice, které kombinují řetízkové n-tice, a sady pravidel přepisování. Všechny funkce složení mají formu ${ displaystyle f ( langle x_ {1}, ..., x_ {m} rangle, langle y_ {1}, ..., y_ {n} rangle, ...) = gamma}$ , kde ${ displaystyle gamma}$ je buď jediná řazená řazená kolekce členů, nebo nějaké použití (potenciálně odlišné) funkce kompozice, která se redukuje na řetízkovou řazenou kolekci členů. Pravidla pro přepis vypadají ${ displaystyle X až f (Y, Z, ...)}$ , kde ${ displaystyle Y}$ , ${ displaystyle Z}$ , ... jsou řetězcové n-tice nebo nekoncové symboly.

Sémantika přepisu GCFG je poměrně přímočará. Výskyt neterminálního symbolu je přepsán pomocí pravidel přepisu jako v bezkontextové gramatice, přičemž nakonec vzniknou pouze kompozice (funkce kompozice aplikované na řetízkové n-tice nebo jiné kompozice). Potom se použijí funkce kompozice, které postupně redukují n-tice na jednu n-tici.

Příklad

Jednoduchý překlad bezkontextové gramatiky do GCFG lze provést následujícím způsobem. Vzhledem k gramatice v (1), který generuje jazyk palindromu ${ displaystyle {ww ^ {R}: w in {a, b } ^ {*} }}$ , kde ${ displaystyle w ^ {R}}$ je řetězec obráceně ${ displaystyle w}$ , můžeme definovat funkci složení konc jako v (2a) a pravidla přepsání jako v (2b).

{ displaystyle S to epsilon ~ | ~ aSa ~ | ~ bSb}

(1)

{ displaystyle conc ( langle x rangle, langle y rangle, langle z rangle) = langle xyz rangle}

(2a)

{ displaystyle S to conc ( langle epsilon rangle, langle epsilon rangle, langle epsilon rangle) ~ | ~ conc ( langle a rangle, S, langle a rangle) ~ | ~ conc ( langle b rangle, S, langle b rangle)}

(2b)

Produkce CF z abbbba je

S

jako

abSba

abbSbba

abbbba

a odpovídající produkce GCFG je

{ displaystyle S to conc ( langle a rangle, S, langle a rangle)}

{ displaystyle conc ( langle a rangle, conc ( langle b rangle, S, langle b rangle), langle a rangle)}

{ displaystyle conc ( langle a rangle, conc ( langle b rangle, conc ( langle b rangle, S, langle b rangle), langle b rangle), langle a rangle)}

{ displaystyle conc ( langle a rangle, conc ( langle b rangle, conc ( langle b rangle, conc ( langle epsilon rangle, langle epsilon rangle, langle epsilon rangle)) , langle b rangle), langle b rangle), langle a rangle)}

{ displaystyle conc ( langle a rangle, conc ( langle b rangle, conc ( langle b rangle, langle epsilon rangle, langle b rangle), langle b rangle), langle rangle)}

{ displaystyle conc ( langle a rangle, conc ( langle b rangle, langle bb rangle, langle b rangle), langle a rangle)}

{ displaystyle conc ( langle a rangle, langle bbbb rangle, langle a rangle)}

{ displaystyle langle abbbba rangle}

Lineární bezkontextové přepisovací systémy (LCFRS)

Weir (1988)^[1] popisuje dvě vlastnosti kompozičních funkcí, linearitu a pravidelnost. Funkce definovaná jako ${ displaystyle f (x_ {1}, ..., x_ {n}) = ...}$ je lineární právě tehdy, když se každá proměnná objeví nejvýše jednou na obou stranách =, tvorba ${ displaystyle f (x) = g (x, y)}$ lineární, ale ne ${ displaystyle f (x) = g (x, x)}$ . Funkce definovaná jako ${ displaystyle f (x_ {1}, ..., x_ {n}) = ...}$ je normální, pokud má levá a pravá strana přesně stejné proměnné, takže ${ displaystyle f (x, y) = g (y, x)}$ pravidelné, ale ne ${ displaystyle f (x) = g (x, y)}$ nebo ${ displaystyle f (x, y) = g (x)}$ .

Gramatika, ve které jsou všechny kompoziční funkce lineární i pravidelné, se nazývá Lineární bezkontextový přepisovací systém (LCFRS). LCFRS je a správná podtřída GCFG, tj. má přísně menší výpočetní výkon než GCFG jako celek.

Na druhou stranu jsou LCFRS přísně výraznější než lineárně indexované gramatiky a jejich slabě ekvivalentní varianta strom sousední gramatiky (ZNAČKY).^[2] Hlava gramatiky je dalším příkladem LCFRS, který je přísně méně výkonný než třída LCFRS jako celek.

LCFRS jsou slabě ekvivalentní (set-local) vícesložkový ZNAČKY (MCTAG ) a také s vícekontextová gramatika (MCFG [1] ).^[3] a minimalistické gramatiky (MG). Jazyky generované LCFRS (a jejich slabě ekvivalentní) lze analyzovat polynomiální čas.^[4]

Viz také

Gramatika zřetězení rozsahu

Reference

^ ^A ^b Weir, David Jeremy (září 1988). Charakterizace gramatických formalizmů mírně citlivých na kontext (PDF) (Ph.D.). Papír. AAI8908403. University of Pennsylvania Ann Arbor.
^ Laura Kallmeyer (2010). Analýza nad rámec bezkontextových gramatik. Springer Science & Business Media. p. 33. ISBN 978-3-642-14846-0.
^ Laura Kallmeyer (2010). Analýza nad rámec bezkontextových gramatik. Springer Science & Business Media. p. 35-36. ISBN 978-3-642-14846-0.
^ Johan F.A.K. van Benthem; Alice ter Meulen (2010). Příručka logiky a jazyka (2. vyd.). Elsevier. p. 404. ISBN 978-0-444-53727-0.

[weir1988-1] A ^b Weir, David Jeremy (září 1988). Charakterizace gramatických formalizmů mírně citlivých na kontext (PDF) (Ph.D.). Papír. AAI8908403. University of Pennsylvania Ann Arbor.

[Kallmeyer2010-2] Laura Kallmeyer (2010). Analýza nad rámec bezkontextových gramatik. Springer Science & Business Media. p. 33. ISBN 978-3-642-14846-0.

[Kallmeyer2010b-3] Laura Kallmeyer (2010). Analýza nad rámec bezkontextových gramatik. Springer Science & Business Media. p. 35-36. ISBN 978-3-642-14846-0.

[BenthemMeulen2010-4] Johan F.A.K. van Benthem; Alice ter Meulen (2010). Příručka logiky a jazyka (2. vyd.). Elsevier. p. 404. ISBN 978-0-444-53727-0.

[1]

[2]

[3]

[4]