Řízená gramatika - Controlled grammar

tento článek možná matoucí nebo nejasné čtenářům. Prosím, pomoz nám objasnit článek. O tom by mohla být diskuse diskusní stránka. (Listopadu 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Řízené gramatiky^[1] jsou třídou gramatiky které se obvykle prodlužují bezkontextové gramatiky s dalšími ovládacími prvky odvození a věta v jazyce. Existuje celá řada různých druhů řízených gramatik, přičemž jde o čtyři hlavní divize Indexované gramatiky, gramatiky s předepsanými derivačními sekvencemi, gramatiky s kontextovými podmínkami pro aplikaci pravidel a gramatiky s rovnoběžnost v aplikaci pravidla. Protože indexované gramatiky jsou v oboru tak dobře zavedené, bude se tento článek zabývat pouze posledně uvedenými třemi druhy řízených gramatik.

Ovládání předepsanými sekvencemi

Gramatiky s předepsanými sekvencemi jsou gramatiky, ve kterých je nějakým způsobem omezena sekvence aplikace pravidel. Existují čtyři různé verze předepsaných sekvenčních gramatik: jazykově řízené gramatiky (často nazývané právě řízené gramatiky), maticové gramatiky, vektorové gramatiky a programované gramatiky.

Ve standardním bezkontextovém gramatickém formalismu se na samotnou gramatiku pohlíží jako na 4-n-tice, ${ displaystyle G = (N, T, S, P)}$, kde N je sada nekoncové / frázové symboly, T je nesouvislá sada symbolů terminálu / slova, S je speciálně určený počáteční symbol vybraný z N, a P je soubor výrobních pravidel jako ${ displaystyle X to alpha}$, kde X je nějaký člen N, a ${ displaystyle alpha}$ je nějaký člen ${ displaystyle (N cup T) ^ {*}}$.

Produkce nad takovou gramatikou jsou sekvence pravidel v P že při použití v pořadí podle sekvence vede k terminálovému řetězci. To znamená, že lze zobrazit množinu představitelných derivací v G jako soubor ${ displaystyle {p_ {1} p_ {2} ... p_ {n}: n geq 0 }}$a jazyk jazyka G jako sada koncových řetězců ${ displaystyle L (G) = {w v T ^ {*}: S Rightarrow _ {p_ {1}} ... Rightarrow _ {p_ {n}} w }}$. Kontrolní gramatiky berou tuto definici jazyka generovaného gramatikou vážně a konkretizují množinu derivací jako aspekt gramatiky. Předepsaná gramatika řízená sekvencí je tedy alespoň přibližně 5 n-ticí ${ displaystyle G = (N, T, S, P, R)}$ kde všechno kromě R je stejný jako v CFG a R je nekonečná sada platných derivačních sekvencí ${ displaystyle p_ {1} p_ {2} ... p_ {n}}$.

Sada R, kvůli své nekonečnosti, je téměř vždy (i když ne nutně) popsán pomocí nějakého pohodlnějšího mechanismu, jako je gramatika (jako v jazykově řízených gramatikách), nebo sada matic nebo vektorů (jako v matici a vektorové gramatiky). Různé variace předepsaných sekvenčních gramatik se tak liší podle toho, jak je sekvence derivací definována na bezkontextové bázi. Protože maticové gramatiky a vektorové gramatiky jsou v zásadě speciální případy jazykově řízených gramatik, níže nebudou uvedeny příklady prvních dvou.

Jazykově řízené gramatiky

Jazykově řízené gramatiky jsou gramatiky, ve kterých produkční sekvence představují dobře definovaný jazyk libovolné povahy, obvykle, i když ne nutně pravidelný, nad množinou (opět obvykle, i když ne nutně) pravidel bezkontextové produkce. Často také mají šestou sadu v gramatické n-tici, což ji dělá ${ displaystyle G = (N, T, S, P, R, F)}$, kde F je soubor inscenací, které se mohou aplikovat vakuově. Tato verze jazykově řízených gramatik, která má takzvanou „kontrolu vzhledu“, je ta od nynějška.

Důkaz-teoretický popis

Nechali jsme pravidelně kontrolovanou bezkontextovou gramatiku s kontrolou vzhledu n-ticí ${ displaystyle G = (N, T, S, P, R, F)}$ kde N, T, S, a P jsou definovány jako v CFG, R je podmnožinou P * tvořící běžný jazyk P, a F je nějaká podmnožina P. Poté definujeme vztah okamžitě odvozený ${ displaystyle Rightarrow _ {p_ {i}}}$ jak následuje:

Vzhledem k několika řetězcům X a y, jak V. .. tak v ${ displaystyle (N cup T) ^ {*}}$, a některé pravidlo ${ displaystyle p = A to w in P}$,

${ displaystyle x Rightarrow _ {p} ^ {ac} y}$

platí pokud

${ displaystyle x = x_ {1} Sekera_ {2}}$ a ${ displaystyle y = y_ {1} wy_ {2}}$nebo

${ displaystyle x = y}$ a ${ displaystyle p ve F}$

Intuitivně to jednoduše vysvětluje, že pravidlo lze použít na řetězec, pokud se v tomto řetězci objeví jeho levá strana, nebo pokud je pravidlo v sadě „vakuově použitelných“ pravidel, která se mohou „použít“ na řetězec bez cokoli měnit. Tento požadavek, který musí platit nevakuově použitelná pravidla, je aspektem kontroly gramatiky. Jazyk pro tento druh gramatiky je pak jednoduše sada terminálových řetězců ${ displaystyle L (G) = {w v T ^ {*}: S Rightarrow _ {p_ {1}} ^ {ac} w_ {1} Rightarrow _ {p_ {2}} ^ {ac} w_ {2} Rightarrow _ {p_ {3}} ^ {ac} ... Rightarrow _ {p_ {n}} ^ {ac} w, for some p_ {1} p_ {2} .. .p_ {n} v R }}$.

Příklad

Zvažte jednoduchou (i když ne nejjednodušší) bezkontextovou gramatiku, která generuje jazyk ${ displaystyle {a ^ {n}: n geq 1 }}$:

Nechat ${ displaystyle G = ( {S, A, X }, {a }, S, {f, g, h, k, l })}$, kde

${ displaystyle f: S až AA}$

${ displaystyle g: S až X}$

${ displaystyle h: A až S}$

${ displaystyle k: A až X}$

${ displaystyle l: S k a}$

V jazykově řízené formě je tato gramatika jednoduše ${ displaystyle G ^ { prime} = ( {S, A, X }, {a }, S, {f, g, h, k, l }, (f | g | h | k | l) ^ {*}, {f, g, h, k, l })}$ (kde ${ displaystyle (f | g | h | k | l) ^ {*}}$ je regulární výraz označující množinu všech sekvencí produkčních pravidel). Jednoduchá modifikace této gramatiky, změna je sada kontrolních sekvencí R do sady ${ displaystyle (f ^ {*} gh ^ {*} k) ^ {*} l ^ {*}}$a změna jeho prázdného souboru pravidel F na ${ displaystyle {g, k }}$, získá gramatiku, která generuje jazyk bez CF. ${ displaystyle {a ^ {2 ^ {n}}: n geq 0 }}$. Chcete-li zjistit, jak, zvažte obecný případ nějakého řetězce s n instance S v něm, tj. ${ displaystyle S ^ {n}}$ (zvláštní případ ${ displaystyle S ^ {1}}$ triviálně odvozuje řetězec A který je ${ displaystyle a ^ {2 ^ {0}}}$, nezajímavý fakt).

Pokud bychom zvolili libovolnou výrobní sekvenci ${ displaystyle f ^ {u} gh ^ {v} k ...}$, můžeme zvážit tři možnosti: ${ displaystyle n = u}$, ${ displaystyle n$, a ${ displaystyle n> u}$ Když ${ displaystyle n = u}$ přepíšeme všechny n instance S tak jako AA, uplatněním pravidla F do řetězce u krát a pokračujte v podávání žádosti G, který platí vakuově (na základě pobytu v F). Když ${ displaystyle n$, přepíšeme všechny n instance S tak jako AAa poté zkuste provést n + 1 přepsat pomocí pravidla F, ale to selže, protože už nejsou žádné Spřepsat a F není v F a tak se nemůže aplikovat vakuově, tedy když ${ displaystyle n$, derivace selže. Nakonec tedy ${ displaystyle n> u}$přepisujeme u instance S, přičemž je ponechána alespoň jedna instance S přepsat následnou aplikací G, přepis S tak jako X. Vzhledem k tomu, že žádné pravidlo této gramatiky nikdy nepřepíše X, taková derivace je určena k tomu, aby nikdy nevytvořila koncový řetězec. Tedy pouze derivace s ${ displaystyle n = u}$ někdy úspěšně přepíše řetězec ${ displaystyle S ^ {n}}$. Podobné argumenty platí pro počet As a proti. Obecně tedy můžeme říci, že strukturu mají pouze platné derivace ${ displaystyle S ^ {n} Rightarrow _ {f} ... Rightarrow _ {f} A ^ {2n} Rightarrow {g} A ^ {2n} Rightarrow {h} ... Rightarrow {h } S ^ {2n} Rightarrow {k} S ^ {2n}}$ vytvoří koncové řetězce gramatiky. The X pravidla v kombinaci se strukturou kontroly v podstatě přinutí všechny Spřepsat jako AAs před jakýmkoli Aje přepsáno na Ss, což je opět nuceno stát se před všemi ještě pozdějšími iteracemi přes S-to-AA cyklus. Nakonec Ss jsou přepsány jako As. Tímto způsobem se počet Ss zdvojnásobuje každý pro každou instanci ${ displaystyle f ^ {8} gh ^ {*} k}$ který se objeví v posloupnosti odvozující terminál.

Při výběru dvou náhodných sekvencí, které nejsou odvozeny z terminálu, a jedné z terminálních derivací, můžeme to vidět v práci:

Nechat ${ displaystyle s_ {1} = ffghkll}$, pak dostaneme neúspěšnou derivaci:

${ displaystyle S Rightarrow _ {f} ^ {ac} AA Rightarrow _ {f} ^ {ac} { text {chyba: f nelze použít, žádné S k přepsání}}}$

Nechat ${ displaystyle s_ {2} = fghhhkll}$, pak dostaneme neúspěšnou derivaci:

${ displaystyle S Rightarrow _ {f} ^ {ac} AA Rightarrow _ {g} ^ {ac} AA Rightarrow _ {h} ^ {ac} SA Rightarrow _ {h} ^ {ac} SS Rightarrow _ {h} ^ {ac} { text {chyba: h nelze použít, žádné A k přepsání}}}$

Nechat ${ displaystyle s_ {3} = fghhkll}$, pak získáme úspěšnou derivaci:

${ displaystyle S Rightarrow _ {f} ^ {ac} AA Rightarrow _ {g} ^ {ac} AA Rightarrow _ {h} ^ {ac} SA Rightarrow _ {h} ^ {ac} SS Rightarrow _ {k} ^ {ac} SS Rightarrow _ {l} ^ {ac} aS Rightarrow _ {l} ^ {ac} aa}$

Podobné derivace s druhým cyklem ${ displaystyle f ^ {*} gh ^ {*} k}$ pouze vyrábět SSSS. Zobrazuje se pouze (pokračující) úspěšná derivace:

${ displaystyle ... Rightarrow SS Rightarrow _ {f} ^ {ac} AAS Rightarrow _ {f} ^ {ac} AAAA Rightarrow _ {g} ^ {ac} AAAA}$

${ displaystyle Rightarrow _ {h} ^ {ac} SAAA Rightarrow _ {h} ^ {ac} SSAA Rightarrow _ {h} ^ {ac} SSSA Rightarrow _ {h} ^ {ac} SSSS Rightarrow _ {k} ^ {ac} SSSS}$

${ displaystyle Rightarrow _ {l} ^ {ac} aSSS Rightarrow _ {l} ^ {ac} aaSS Rightarrow _ {l} ^ {ac} aaaS Rightarrow _ {l} ^ {ac} aaaa}$

Maticové gramatiky

Maticové gramatiky (rozšířené o své vlastní článek ) jsou zvláštním případem pravidelných kontrolovaných bezkontextových gramatik, ve kterých je jazyk produkční sekvence ve formě ${ displaystyle (m_ {1} | m_ {2} | ... | m_ {n}) ^ {*}}$, kde každá „matice“ ${ displaystyle m_ {i}}$ je jedna sekvence. Pro zjednodušení není taková gramatika reprezentována překročením gramatiky P, ale spíše pouze se sadou matic namísto pravidel jazyka a produkce. Maticová gramatika je tedy pětinásobnou n-ticí ${ displaystyle G = (N, T, M, S, F)}$, kde N, T, S, a F jsou definovány v zásadě jako dříve provedené (s F podmnožina M tentokrát) a M je sada matic ${ displaystyle m_ {i} = p_ {i, 1} p_ {i, 2} ... p_ {i, n_ {i}}}$ kde každý ${ displaystyle p_ {i, j}}$ je bezkontextové produkční pravidlo.

Odvozený vztah v maticové gramatice je tedy definován jednoduše jako:

Vzhledem k několika řetězcům X a y, jak V. .. tak v ${ displaystyle (N cup T) ^ {*}}$a nějaká matice ${ displaystyle m = p_ {1} p_ {2} ... p_ {n} v M}$,

${ displaystyle x Rightarrow _ {m} ^ {ac} y}$

platí pokud

${ displaystyle x = x_ {1} Sekera_ {2}}$, ${ displaystyle y = y_ {1} wy_ {2}}$, a ${ displaystyle A Rightarrow _ {p_ {1}} ^ {ac} w_ {1} Rightarrow _ {p_ {2}} ^ {ac} w_ {2} Rightarrow _ {p_ {3}} ^ {ac } ... Rightarrow _ {p_ {n}} ^ {ac} w}$nebo

${ displaystyle x = y}$ a ${ displaystyle m v F}$

Neformálně je maticová gramatika jednoduše gramatikou, ve které se během každého přepisovacího cyklu musí provádět určitá posloupnost operací přepisování, nikoli pouze jedna operace přepisování, tj. Jedno pravidlo „spouští“ kaskádu dalších pravidel. Podobné jevy lze provádět ve standardním kontextově citlivém idiomu, jak je tomu ve fonologii založené na pravidlech a dříve Transformační gramatika, takzvanými pravidly „krmení“, která mění derivaci takovým způsobem, aby poskytla prostředí pro nepovinné pravidlo, které na ni bezprostředně navazuje.

Vektorové gramatiky

Vektorové gramatiky úzce souvisí s maticovými gramatikami a ve skutečnosti je lze považovat za speciální třídu maticových gramatik, ve které pokud ${ displaystyle m v M}$, pak také všechny jeho obměny ${ displaystyle p (m)}$. Pro větší pohodlí však budeme definovat vektorové gramatiky následovně: vektorová gramatika je n-tice ${ displaystyle G = (N, T, M, S, F)}$, kde N, T, a F jsou definovány dříve (F být podmnožinou M znovu) a kde M je sada vektorů ${ displaystyle m_ {i} = {p_ {1}, p_ {2}, ..., p_ {n} }}$, přičemž každý vektor je souborem pravidel bez kontextu.

Odvozený vztah ve vektorové gramatice je pak:

Vzhledem k několika řetězcům X a y, jak V. .. tak v ${ displaystyle (N cup T) ^ {*}}$a nějaká matice ${ displaystyle m = {p_ {1}, p_ {2}, ..., p_ {n} } v M}$,

${ displaystyle x Rightarrow _ {m} ^ {ac} y}$

platí pokud

${ displaystyle x = x_ {1} Sekera_ {2}}$, ${ displaystyle y = y_ {1} wy_ {2}}$, a ${ displaystyle A Rightarrow _ {p_ {i_ {1}}} ^ {ac} w_ {1} Rightarrow _ {p_ {i_ {2}}} ^ {ac} w_ {2} Rightarrow _ {p_ { i_ {3}}} ^ {ac} ... Rightarrow _ {p_ {i_ {n}}} ^ {ac} w}$, kde ${ displaystyle m = {p_ {i_ {1}}, p_ {i_ {2}}, ..., p_ {i_ {n}} }}$nebo

${ displaystyle x = y}$ a ${ displaystyle m v F}$

Všimněte si, že počet produkčních pravidel použitých v odvozovací sekvenci, n, je stejný jako počet produkčních pravidel ve vektoru. Neformálně je tedy vektorová gramatika gramatikou, ve které je aplikována sada produkcí, přičemž každá produkce je aplikována přesně jednou, v libovolném pořadí, k odvození jednoho řetězce od druhého. Vektorové gramatiky jsou tedy téměř identické s maticovými gramatikami, mínus omezení pořadí, v jakém musí produkce probíhat během každého cyklu aplikace pravidel.

Naprogramované gramatiky

Programované gramatiky jsou relativně jednoduchým rozšířením bezkontextových gramatik s ovládáním derivace podle pravidel. Naprogramovaná gramatika je čtyřnásobná n-tice ${ displaystyle G = (N, T, S, P)}$, kde N, T, a S jsou jako v bezkontextové gramatice a P je sada n-tic ${ displaystyle (p, sigma, phi)}$, kde str je bezkontextové produkční pravidlo, ${ displaystyle sigma}$ je podmnožinou P (nazývá se pole úspěchu) a ${ displaystyle phi}$ je podmnožinou P (nazývá se pole selhání). Pokud je pole selhání každého pravidla v P je prázdné, v gramatice chybí kontrola vzhledu a pokud alespoň jedno pole selhání není prázdné, má gramatika kontrolu vzhledu. Relace odvození na naprogramované gramatice je definována takto:

Vzhledem k tomu, dva řetězce ${ displaystyle x, y in (N cup T) ^ {*}}$, a některé pravidlo ${ displaystyle p = (A to w, sigma, phi) v P}$,

${ displaystyle x Rightarrow _ {p} y}$ a ${ displaystyle x = x'Ax '', y = x'wx ''}$nebo

${ displaystyle x = y}$ a A se nezobrazí v x.

Jazyk programované gramatiky G je definována omezením odvození podle pravidla, jako ${ displaystyle L (G) = {w in (N cup T) ^ {*}: S Rightarrow _ {p_ {1}} w_ {1} Rightarrow _ {p_ {2}} ... Rightarrow _ {p_ {n}} s }}$, kde pro každého ${ displaystyle p_ {i} = (A_ {i} až v_ {i}, sigma _ {i}, phi _ {i})}$, buď ${ displaystyle w_ {i-1} = x_ {i-1} Sekera '_ {i-1}, w_ {i} = x_ {i-1} v_ {i} x' _ {i-1}, a p_ {i + 1} in sigma _ {i}}$ nebo ${ displaystyle w_ {i-1} = w_ {i}, p_ {i + 1} in phi _ {i}}$.

Intuitivně při aplikaci pravidla str v naprogramované gramatice může pravidlo buď úspěšně přepsat symbol v řetězci, v takovém případě musí být následující pravidlo v strv poli úspěchu, nebo může pravidlo selhat při přepsání symbolu (aplikuje se tedy vakuově), v takovém případě musí být následující pravidlo v strpole selhání. Volba pravidla, které se má použít na počáteční řetězec, je na rozdíl od gramatiky ovládané jazykem libovolná, ale jakmile je proveden výběr, pravidla, která lze použít poté, co od tohoto okamžiku omezí posloupnost pravidel.

Příklad

Stejně jako u tolika řízených gramatik mohou programované gramatiky generovat jazyk ${ displaystyle {a ^ {2 ^ {n}}: n geq 0 }}$:

Nechat ${ displaystyle G = ( {S, A }, {a }, S, {r_ {1}, r_ {2}, r_ {3} })}$, kde

${ displaystyle r_ {1} = (S až AA, {r_ {1} }, {r_ {2} })}$

${ displaystyle r_ {2} = (A až S, {r_ {2} }, {r_ {1}, r_ {3} })}$

${ displaystyle r_ {3} = (S až a, {r_ {3} }, prázdná sada)}$

Odvození řetězce aaaa je následující:

${ displaystyle S Rightarrow _ {r_ {1}} AA Rightarrow _ {r_ {1}} AA Rightarrow _ {r_ {2}} SA Rightarrow _ {r_ {2}} SS Rightarrow _ {r_ { 2}} SS}$

${ displaystyle Rightarrow _ {r_ {1}} AAS Rightarrow _ {r_ {1}} AAAA Rightarrow _ {r_ {1}} AAAA}$

${ displaystyle Rightarrow _ {r_ {2}} SAAA Rightarrow _ {r_ {2}} SSAA Rightarrow _ {r_ {2}} SSSA Rightarrow _ {r_ {2}} SSSS Rightarrow _ {r_ {2 }} SSSS}$

${ displaystyle Rightarrow _ {r_ {3}} aSSS Rightarrow _ {r_ {3}} aaSS Rightarrow _ {r_ {3}} aaaS Rightarrow _ {r_ {3}} aaaa Rightarrow _ {r_ {3 }} aaaa}$

Jak je patrné z odvození a pravidel, pokaždé ${ displaystyle r_ {1}}$ a ${ displaystyle r_ {2}}$ uspějí, vrací se zpět k sobě, což nutí každé pravidlo pokračovat v přepisování řetězce znovu a znovu, dokud to již nebude moci udělat. Při selhání může derivace přejít na jiné pravidlo. V případě ${ displaystyle r_ {1}}$, to znamená přepsat vše Ss as AAs, poté přepněte na ${ displaystyle r_ {2}}$. V případě ${ displaystyle r_ {2}}$, to znamená přepsat vše As as Ss, poté přepněte buď na ${ displaystyle r_ {1}}$, což povede ke zdvojnásobení počtu Ss vyrábí, nebo do ${ displaystyle r_ {3}}$ který převádí Ss až As pak zastaví derivaci. Každý cyklus projde ${ displaystyle r_ {1}}$ pak ${ displaystyle r_ {2}}$ proto buď zdvojnásobí počáteční počet Ss, nebo převede Ss až As. Triviální případ generování A, v případě, že je obtížné to vidět, jednoduše zahrnuje prázdnou aplikaci ${ displaystyle r_ {1}}$, čímž skočíte rovnou na ${ displaystyle r_ {2}}$ což také vakuově platí, pak skočit na ${ displaystyle r_ {3}}$ který vyrábí A.

Ovládání podle kontextových podmínek

Na rozdíl od gramatik řízených předepsanými sekvencemi produkčních pravidel, která omezují prostor platných derivací, ale neomezují druhy vět, na které se může produkční pravidlo vztahovat, gramatiky ovládané kontextovými podmínkami nemají žádná omezení sekvence, ale umožňují omezení různé složitosti na věty, na které se vztahuje výrobní pravidlo. Podobně jako u gramatik řízených předepsanými posloupnostmi existuje několik různých druhů gramatik řízených kontextovými podmínkami: podmíněné gramatiky, semi-podmíněné gramatiky, náhodné kontextové gramatiky a uspořádané gramatiky.

Podmíněné gramatiky

Podmíněné gramatiky jsou nejjednodušší verzí gramatik ovládaných kontextovými podmínkami. Struktura podmíněné gramatiky je velmi podobná struktuře normální gramatiky přepisování: ${ displaystyle G = (N, T, S, P)}$, kde N, T, a S jsou definovány v bezkontextové gramatice a P je sada dvojic formuláře ${ displaystyle (p, R)}$ kde str je produkční pravidlo (obvykle bezkontextové) a R je jazyk (obvykle běžný) ${ displaystyle N cup T}$. Když R je pravidelný, R lze vyjádřit jako regulární výraz.

Důkaz-teoretická definice

S touto definicí podmíněné gramatiky můžeme definovat odvozenou relaci takto:

Vzhledem k tomu, dva řetězce ${ displaystyle x, y in (N cup T) ^ {*}}$a nějaká pravidla produkce ${ displaystyle p = (A až w, R) v P}$,

${ displaystyle x Rightarrow _ {p} y}$ kdyby a jen kdyby ${ displaystyle x = x'Ax ''}$, ${ displaystyle y = x'wx ''}$, a ${ displaystyle x v R}$

Neformálně pak produkční pravidlo pro pár v P lze použít pouze na řetězce, které jsou v jeho kontextu. Tedy například kdybychom měli pár ${ displaystyle (S až x, a ^ {*} Sb ^ {*})}$, můžeme to použít pouze na řetězce skládající se z libovolného počtu As následuje pouze přesně S následuje libovolný počet bs, tj. na věty v ${ displaystyle {a ^ {m} Ab ^ {n}: m, n geq 0 }}$, například řetězce S, aSb, aaaS, aSbbbbbbatd. Nelze použít na řetězce typu xSy, aaaSxbbb, atd.

Příklad

Podmíněné gramatiky mohou generovat kontextový jazyk ${ displaystyle {a ^ {2 ^ {n}}: n geq 0 }}$.

Nechat ${ displaystyle G = ( {S, S '}, {a }, {f, g, h }, S)}$, kde

${ displaystyle f = (S až AA, A ^ {*} S ^ {+})}$

${ displaystyle g = (A až B, B ^ {*} A ^ {+})}$

${ displaystyle h = (B až S, S ^ {*} B ^ {+})}$

${ displaystyle k = (S k a, a ^ {*} S ^ {+})}$

Potom můžeme vygenerovat větu aaaa s následujícím odvozením:

${ displaystyle S Rightarrow _ {f} AA Rightarrow _ {g} BA Rightarrow _ {g} BB}$

${ displaystyle Rightarrow _ {h} SB Rightarrow _ {h} SS Rightarrow _ {f} AAS Rightarrow _ {f} AAAA}$

${ displaystyle Rightarrow _ {g} BAAA Rightarrow _ {g} BBAA Rightarrow _ {g} BBBA Rightarrow _ {g} BBBB}$

${ displaystyle Rightarrow _ {h} SBBB Rightarrow _ {h} SSBB Rightarrow _ {h} SSSB Rightarrow _ {h} SSSS}$

${ displaystyle Rightarrow _ {k} aSSS Rightarrow _ {k} aaSS Rightarrow _ {k} aaaS Rightarrow _ {k} aaaa}$

Polopodmíněné gramatiky

Semi-podmíněná gramatika je velmi podobná podmíněné gramatice a technicky je třída semi-podmíněné gramatiky podmnožinou podmíněných gramatik. Spíše než specifikovat, jak musí celý řetězec vypadat, aby pravidlo mohlo platit, semi-podmíněné gramatiky určují, že řetězec musí mít jako podřetězce všechny některé sady řetězců a žádnou jinou sadu, aby mohlo pravidlo platit . Formálně je tedy semi-podmíněná gramatika n-ticí ${ displaystyle G = (N, T, S, P)}$kde N, T, a S jsou definovány jako v CFG a P je soubor pravidel jako ${ displaystyle (p, R, Q)}$ kde str je (obvykle bezkontextové) produkční pravidlo a R a Q jsou konečné sady řetězců. Odvozený vztah lze potom definovat následovně.

Pro dva struny ${ displaystyle xAx ', xwx' in (N cup T) ^ {*}}$, a některé pravidlo ${ displaystyle p = (A až w, R, Q) v P}$,

${ displaystyle xAx ' Rightarrow _ {p} xwx'}$ právě když každý řetězec v R je podřetězec z ${ displaystyle xAx '}$a žádný řetězec v Q je podřetězec z ${ displaystyle xAx '}$

Jazyk semi-podmíněné gramatiky je pak triviálně množina terminálových řetězců ${ displaystyle L (G) = {w v T ^ {*}: S Rightarrow ^ {*} w }}$.

Níže je uveden příklad semi-podmíněné gramatiky, který slouží také jako příklad gramatik s náhodným kontextem.

Náhodné kontextové gramatiky

Náhodná kontextová gramatika je polopodmíněná gramatika, ve které R a Q sady jsou všechny podskupiny N. Protože podmnožiny N jsou konečné sady ${ displaystyle (N cup T) ^ {*}}$, je jasné, že gramatiky s náhodným kontextem jsou skutečně druhy semi-podmíněných gramatik.

Příklad

Stejně jako podmíněné gramatiky mohou gramatiky s náhodným kontextem (a tedy i částečně podmíněné gramatiky) generovat jazyk ${ displaystyle {a ^ {2 ^ {n}}: n geq 0 }}$. Jedna gramatika, která to dokáže, je:

Nechat ${ displaystyle G = ( {S, X, Y, A }, {a }, S, {r_ {1}, r_ {2}, r_ {3}, r_ {4}, r_ { 5} })}$, kde

${ displaystyle r_ {1} = (S až XX, prázdná sada, {Y, A })}$

${ displaystyle r_ {2} = (X až Y, prázdná sada, {S })}$

${ displaystyle r_ {3} = (Y až S, prázdná sada, {X })}$

${ displaystyle r_ {4} = (S až A, prázdná sada, {X })}$

${ displaystyle r_ {5} = (A až a, prázdná množina, {S })}$

Zvažte nyní produkci pro aaaa:

${ displaystyle S Rightarrow _ {r_ {1}} XX Rightarrow _ {r_ {2}} YX Rightarrow _ {r_ {2}} YY Rightarrow _ {r_ {3}} SY Rightarrow _ {r_ { 3}} SS}$

${ displaystyle Rightarrow _ {r_ {1}} XXS Rightarrow _ {r_ {1}} XXXX Rightarrow _ {r_ {2}} YXXX Rightarrow _ {r_ {2}} YYXX Rightarrow _ {r_ {2 }} RRRR Rightarrow _ {r_ {2}} RRRR}$

${ displaystyle Rightarrow _ {r_ {3}} SYYY Rightarrow _ {r_ {3}} SSYY Rightarrow _ {r_ {3}} SSSY Rightarrow _ {r_ {3}} SSSS}$

${ displaystyle Rightarrow _ {r_ {4}} ASSS Rightarrow _ {r_ {4}} AASS Rightarrow _ {r_ {4}} AAAS Rightarrow _ {r_ {4}} AAAA}$

${ displaystyle Rightarrow _ {r_ {5}} aAAA Rightarrow _ {r_ {5}} aaAA Rightarrow _ {r_ {5}} aaaA Rightarrow _ {r_ {5}} aaaa}$

Chování R sady zde jsou triviální: libovolný řetězec lze přepsat podle nich, protože nevyžadují přítomnost žádných podřetězců. Chování Q sady jsou však zajímavější. v ${ displaystyle r_ {1}}$, jsme nuceni Q přepsán S, čímž začíná S-dvojnásobný proces, pouze když ne Ys nebo As jsou přítomny v řetězci, což znamená, pouze když je předchozí S- proces zdvojnásobení byl plně zahájen, což vylučuje možnost pouze zdvojnásobení některých z Ss. v ${ displaystyle r_ {2}}$, který přesouvá S- zdvojnásobení procesu do druhé fáze, nemůžeme zahájit tento proces, dokud nebude dokončena první fáze a nebudou již žádné Ss pokusit se zdvojnásobit, protože Q set zabrání použití pravidla, pokud existuje S symbol stále v řetězci. v ${ displaystyle r_ {3}}$dokončujeme fázi zdvojnásobení zavedením Szpět jen tehdy, když už nejsou Xs přepsat, tedy až bude druhá fáze dokončena. Můžeme procházet těmito fázemi tolikrát, kolikrát chceme, a přepsat je všechny Ss až XXs před přepsáním každého z nich X na Y a pak na každou Y do S, nakonec končí jejich nahrazením S s A a pak A. Protože pravidlo pro výměnu S s A zakazuje aplikaci na řetězec s X v tom to nemůžeme aplikovat uprostřed první fáze S- zdvojnásobení procesu, což nám opět znemožňuje pouze zdvojnásobení některých Ss.

Objednané gramatiky

Uspořádané gramatiky jsou možná jedním z jednodušších rozšíření gramatik do kontrolované gramatické domény. Objednaná gramatika je prostě n-tice ${ displaystyle G = (N, T, S, P)}$ kde N, T, a S jsou totožné s těmi v CFG a P je sada pravidel přepisu bez kontextu s částečným uspořádáním ${ displaystyle <}$. Částečné uspořádání se poté použije k určení, které pravidlo se má použít na řetězec, když je použitelné více pravidel. Odvozený vztah je pak:

Vzhledem k několika řetězcům ${ displaystyle xAx ', xwx' in (N cup T) ^ {*}}$ a nějaké pravidlo ${ displaystyle p = A to w in P}$,

${ displaystyle xAx ' Rightarrow _ {p} xwx'}$ právě tehdy, pokud neexistuje žádné pravidlo ${ displaystyle p '= A to w' v P}$ takhle ${ displaystyle p$

.

Příklad

Stejně jako mnoho jiných kontextově řízených gramatik, mohou uspořádané gramatiky vynutit použití pravidel v určitém pořadí. Protože toto je základní vlastnost předchozích gramatik, které by mohly generovat jazyk ${ displaystyle {a ^ {2 ^ {n}}: n geq 0 }}$, nemělo by být žádným překvapením, že gramatika, která výslovně používá řazení pravidel, spíše než kódování pomocí řetězcových kontextů, by měla být podobně schopna zachytit tento jazyk. A jak se ukázalo, právě taková uspořádaná gramatika existuje:

Nechat ${ displaystyle G = ( {S, X, Y, Z, A }, {a }, S, P)}$, kde P je částečně seřazená množina popsaná v Hasseův diagram

Odvození řetězce aaaa je jednoduše:

${ displaystyle S Rightarrow _ {S až XX} XX Rightarrow _ {X k Y} YX Rightarrow _ {X k Y} YY Rightarrow _ {Y k S} SY Rightarrow _ {Y to S} YY}$

${ displaystyle Rightarrow _ {S až XX} XXS Rightarrow _ {S až XX} XXXX}$

${ displaystyle Rightarrow _ {X k Y} YXXX Rightarrow _ {X k Y} YYXX Rightarrow _ {X k Y} YYYX Rightarrow _ {X k Y} YYYY }$

${ displaystyle Rightarrow _ {Y to S} SYYY Rightarrow _ {Y to S} SSYY Rightarrow _ {Y to S} SSSY Rightarrow _ {Y to S} SSSS }$

${ displaystyle Rightarrow _ {S k A} ASSS Rightarrow _ {S k A} AASS Rightarrow _ {S k A} AAAS Rightarrow _ {S k A} AAAA }$

${ displaystyle Rightarrow _ {A to a} aAAA Rightarrow _ {A to a} aaAA Rightarrow _ {A to a} aaaA Rightarrow _ {A to a} aaaa }$

V každém kroku této cesty probíhá derivace přepisováním v cyklech. Všimněte si, že pokud v pátém kroku SY, měli jsme čtyři možnosti: ${ displaystyle Y až Z, S až Z, Y až S, S až A}$, z nichž první dva zastaví derivaci, jako Z nelze přepsat. V příkladu jsme použili ${ displaystyle Y až S}$ odvodit SS, ale zvažte, zda jsme si vybrali ${ displaystyle S do A}$ namísto. Byli bychom vyrobili řetězec TAK JAKO, pro které jsou možnosti ${ displaystyle Y až Z}$ a ${ displaystyle A až Z}$, které oba zastaví derivaci. Tedy s řetězcem SYa naopak YS, musíme přepsat Y k výrobě SS. Stejné pozastavení pro jiné kombinace, takže celkově pořadí donutí derivaci zastavit, jinak bude pokračovat přepsáním všech Ss až XXs, pak všichni Xs až Ys, pak všichni Ys až Ss, a tak dále, pak nakonec vše Ss až Apotom všechny As až As. Tímto způsobem řetězec ${ displaystyle S ^ {n}}$ lze přepsat pouze jako ${ displaystyle A ^ {n}}$ který vyrábí As, nebo jako ${ displaystyle S ^ {2n}}$. Začínání s n = 0, mělo by být jasné, že tato gramatika pouze generuje jazyk ${ displaystyle {a ^ {2 ^ {n}}: n geq 0 }}$.

Gramatiky s paralelismem

Ještě další třídou řízených gramatik je třída gramatik s paralelismem v aplikaci operace přepisování, ve které každý krok přepisování může (nebo musí) přepsat současně více než jeden terminál. I tyto mají několik příchutí: indické paralelní gramatiky, k-gramatiky, gramatiky s rozptýleným kontextem, neuspořádané gramatiky s rozptýleným kontextem a k-jednoduché maticové gramatiky. Opět se varianty liší v tom, jak je definován paralelismus.

Indické paralelní gramatiky

Indická paralelní gramatika je jednoduše CFG, ve kterém se má použít pravidlo přepsání, musí být přepsány všechny instance neterminálního symbolu pravidel současně. Tedy například daný řetězec aXbYcXd, se dvěma případy X, a některé pravidlo ${ displaystyle X to w}$, jediný způsob, jak tento řetězec přepsat tímto pravidlem, je přepsat jako awbYcwd; ani awbYcXd ani aXbYcwd jsou platná přepsání v indické paralelní gramatice, protože nepřepsaly všechny instance X.

Indické paralelní gramatiky mohou snadno vytvořit jazyk ${ displaystyle {ww: w in {a, b } ^ {*} }}$:

Nechat ${ displaystyle G = ( {S, A }, {a, b }, S, {f, g, h, k })}$, kde

${ displaystyle f = S až AA}$

${ displaystyle g = A až aA}$

${ displaystyle h = A až bA}$

${ displaystyle k = A až epsilon}$

Generování aabaab pak je docela jednoduchý:

${ displaystyle S Rightarrow _ {f} AA Rightarrow _ {g} aAaA Rightarrow _ {g} aaAaaA Rightarrow _ {h} aabAaabA Rightarrow _ {k} aabaab}$

Jazyk ${ displaystyle {a ^ {2 ^ {n}}: n geq 0 }}$ je ještě jednodušší:

Nechat ${ displaystyle G = ( {S }, {a }, S, P)}$, kde P skládá se z

${ displaystyle S to SS}$

${ displaystyle S to a}$

Již od prvního pravidla a požadavku, aby byly všechny instance jiného než terminálu přepsány současně se stejným pravidlem, by mělo být zřejmé, že počet Ss se zdvojnásobí v každém přepisovacím kroku pomocí prvního pravidla, čímž se dají odvozovací kroky ${ displaystyle S Rightarrow S ^ {2} Rightarrow S ^ {4} Rightarrow S ^ {8} Rightarrow ...}$. Konečné použití druhého pravidla nahradí všechny Ss s As, což ukazuje, jak tento jednoduchý jazyk může jazyk vytvořit ${ displaystyle {a ^ {2 ^ {n}}: n geq 0 }}$.

K-gramatiky

K-gramatika je ještě další druh paralelní gramatiky, velmi odlišný od indické paralelní gramatiky, ale stále s úrovní paralelismu. V k-gramatice, pro nějaké číslo k, přesně k nekoncové symboly musí být přepsány v každém kroku (s výjimkou prvního kroku, kde jediným symbolem v řetězci je počáteční symbol). Pokud má řetězec méně než k bez terminálů, derivace selže.

3 gramatiky mohou produkovat jazyk ${ displaystyle {a ^ {n} b ^ {n} c ^ {n}: n geq 0 }}$, jak je vidět níže:

Nechat ${ displaystyle G = ( {S, A, B, C }, {a, b, c }, S, P)}$, kde P skládá se z:

${ displaystyle S do ABC}$

${ displaystyle A až aA}$

${ displaystyle A to a}$

${ displaystyle B až bB}$

${ displaystyle B až b}$

${ displaystyle C až cC}$

${ displaystyle C až c}$

S následující derivací pro aaabbbccc:

${ displaystyle S Rightarrow ABC Rightarrow aAbBcC Rightarrow aaAbbBccC Rightarrow aaabbbccc}$

V každém kroku derivace, s výjimkou prvního a posledního, jsme použili autorekurzivní pravidla ${ displaystyle A až aA, B až bB, C až cC}$. Kdybychom nepoužili rekurzivní pravidla, namísto toho řekněme ${ displaystyle A až a, B až bB, C až cC}$, kde jedno z pravidel není samovolně rekurzivní, počet neterminálů by se snížil na 2, čímž by řetězec nemohl být dále odvozován, protože by měl příliš málo neterminálů k přepsání.

Ruské paralelní gramatiky

Ruské paralelní gramatiky^[2] jsou někde mezi indickými paralelními gramatikami a k-gramatikami, definovanými jako ${ displaystyle G = (N, T, S, P)}$, kde N, T, a S jsou jako v bezkontextové gramatice a P je sada párů ${ displaystyle (A to w, k)}$, kde ${ displaystyle A to w}$ je pravidlo bezkonkurenční produkce a k je buď 1 nebo 2. Použití pravidla ${ displaystyle p = (A to w, k)}$ zahrnuje přepsání k výskyty A na w zároveň.

Rozptýlené kontextové gramatiky

Rozptýlená kontextová gramatika je čtyřnásobná n-tice ${ displaystyle G = (N, T, S, P)}$ kde N, T, a S jsou definovány jako v bezkontextové gramatice a P je sada n-tic zvaná matice ${ displaystyle p = (A_ {1} až w_ {1}, ..., A_ {n} až w_ {n})}$, kde ${ displaystyle n> 0}$ se může lišit podle matice. Odvozený vztah pro takovou gramatiku je

${ displaystyle x Rightarrow _ {p} y}$ kdyby a jen kdyby

${ displaystyle p = (A_ {1} až w_ {1}, ..., A_ {n} až w_ {n}) v P}$, a

${ displaystyle x = x_ {1} A_ {1} x_ {2} ... x_ {n} A_ {n} x_ {n + 1}, y = x_ {1} w_ {1} x_ {2}. ..x_ {n} w_ {n} x_ {n + 1}}$, pro ${ displaystyle x_ {i} in (N cup T) ^ {*}}$

Intuitivně pak matice v gramatice s rozptýleným kontextem poskytují seznam pravidel, která musí být každá použita pro neterminály v řetězci, kde se tyto neterminály objevují ve stejném lineárním pořadí jako pravidla, která je přepisují.

Neuspořádaná gramatika rozptýleného kontextu je gramatika rozptýleného kontextu, ve které pro každé pravidlo v P, každá z jeho permutací je také v P. Jako takové lze pravidlo a jeho obměny místo toho reprezentovat jako množinu, nikoli jako n-tice.

Příklad

Rozptýlené kontextové gramatiky dokážou jazyk popsat ${ displaystyle {a ^ {n} b ^ {n} c ^ {n}: n geq 0 }}$ docela snadno.

Nechat ${ displaystyle G = ( {S, A, B, C }, {a, b, c }, S, {r_ {1}, r_ {2}, r_ {3} })}$, kde

${ displaystyle r_ {1} = (S k ABC)}$

${ displaystyle r_ {2} = (A až aA, B až bB, C až cC)}$

${ displaystyle r_ {3} = (A to epsilon, B to epsilon, C to epsilon)}$

Odvození aaabbbccc pak je triviální:

${ displaystyle S Rightarrow _ {r_ {1}} ABC Rightarrow _ {r_ {2}} aAbBcC Rightarrow _ {r_ {2}} aaAbbBccC Rightarrow _ {r_ {2}} aaaAbbbBcccC Rightarrow _ {r_ { 3}} aaabbbccc}$

Reference