Maticová gramatika - Matrix grammar

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Březen 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

A maticová gramatika je formální gramatika ve kterém jsou namísto jednotlivých inscenací seskupeny produkce do konečných sekvencí. Produkci nelze použít samostatně, musí být použita postupně. Při aplikaci takového sledu produkcí se přepis provádí v souladu s každou produkcí v pořadí, první, druhá atd., Dokud se pro přepis nepoužije poslední produkce. Sekvence jsou označovány jako matice.

Maticová gramatika je příponou bezkontextová gramatika a jedna instance a řízená gramatika.

Formální definice

A maticová gramatika je objednaná čtyřnásobná${displaystyle G = (V_ {N}, V_ {T}, X_ {0}, M)}$kde

• ${displaystyle V_ {N}}$ je konečná sada neterminálů
• ${displaystyle V_ {T}}$ je konečná sada terminálů
• ${displaystyle X_ {0}}$ je speciální prvek ${displaystyle V_ {N}}$, viz. počáteční symbol
• ${displaystyle M}$ je konečná sada neprázdných sekvencí, jejichž prvky jsou uspořádané páry ${displaystyle (P, Q)}$ kde

${displaystyle quad Pin V ^ {*} V_ {N} V ^ {*}, quad Qin V ^ {*}, quad V = V_ {N} pohár V_ {T}.}$^[1]

Páry se nazývají produkce, psáno jako ${displaystyle P o Q}$. Sekvence se nazývají matice a lze jej zapsat jako

${displaystyle m = [P_ {1} o Q_ {1}, ldots, P_ {r} o Q_ {r}].}$

Nechat ${displaystyle F}$ být souborem všech produkcí, které se objevují v matricích ${displaystyle m}$ maticové gramatiky ${displaystyle G}$. Pak maticová gramatika ${displaystyle G}$ je typu-${displaystyle i, i = 0,1,2,3}$, prodlužování délky, lineární, ${displaystyle lambda}$-volný, uvolnit, bez kontextu nebo kontextové právě tehdy, pokud jde o gramatiku ${displaystyle G_ {1} = (V_ {N}, V_ {T}, X_ {0}, F)}$ má následující vlastnost.

Pro maticovou gramatiku ${displaystyle G}$, binární relace ${displaystyle Rightarrow _ {G}}$ je definováno; také reprezentován jako ${displaystyle Rightarrow}$. Pro všechny ${displaystyle P, Qin V ^ {*}}$, ${displaystyle PRightarrow Q}$ platí pouze tehdy, pokud existuje celé číslo ${displaystyle rgeq 1}$ taková, že ta slova

${displaystyle alpha _ {1} ,, ldots, alpha _ {r + 1}, quad P_ {1}, ldots, P_ {r}, quad Q_ {1}, ldots, Q_ {r}, quad R_ {1} , ldots, R_ {r}, quad, R ^ {1}, ldots, R ^ {r}}$

přes V existují a

• ${displaystyle alpha _ {1} = P}$ a ${displaystyle alpha _ {r + 1} = Q}$
• ${displaystyle [P_ {1} o Q_ {1}, ldots, P_ {r} o Q_ {r}]}$ je jednou z matic ${displaystyle G}$
• ${displaystyle alpha _ {i} = R_ {i} P_ {i} R ^ {i}}$ a ${displaystyle alpha _ {i + 1} = R_ {i} Q_ {i} R ^ {i}}$ pro všechny ${displaystyle i}$ takhle ${displaystyle 1leq ileq r.}$

Nechat ${displaystyle Rightarrow ^ {*}}$ být reflexivní přechodné uzavření vztahu ${displaystyle Rightarrow}$. Potom jazyk generovaný maticovou gramatikou ${displaystyle G}$ darováno

${displaystyle L (G) = {Pin {V_ {T}} ^ {*} | X_ {0} Rightarrow ^ {*} P}.}$

Příklady

Zvažte maticovou gramatiku

${displaystyle G = ({S, X, Y}, {a, b, c}, S, M)}$

kde ${displaystyle M}$ je kolekce obsahující následující matice:

${displaystyle m_ {0}: [Sightarrow XY], quad m_ {1}: [Xightarrow aXb, Yightarrow cY], quad m_ {2}: [Xightarrow ab, Yightarrow c]}$

Tyto matice, které obsahují pouze bez kontextu pravidla, vygenerujte kontextové Jazyk

${displaystyle L = {a ^ {n} b ^ {n} c ^ {n} | ngeq 1}.}$Přidružené slovo uživatele ${displaystyle a ^ {n} b ^ {n} c ^ {n}}$je${displaystyle Aw (a ^ {n} b ^ {n} c ^ {n}) = m_ {0} m_ {1} ^ {n-2} m_ {2}, forall ngeq 2}$ a ${displaystyle Aw (abc) = m_ {0} m_ {2}}$.

Tento příklad naleznete na stranách 8 a 9 v části ^[1] v následující podobě: Vezměme si maticovou gramatiku

${displaystyle G = ({S, X, Y, Z}, {a, b, c}, S, M)}$

kde ${displaystyle M}$ je kolekce obsahující následující matice:

${displaystyle m_ {0}: [Sightarrow abc], quad m_ {1}: [Sightarrow aXbYcZ], quad m_ {2}: [Xightarrow aX, Yightarrow bY, Zightarrow cZ], quad m_ {3}: [Xightarrow ab, Yightarrow b, Zightarrow c]}$

Tyto matice, které obsahují pouze kontextové pravidelné pravidla, vygenerujte kontextové Jazyk

${displaystyle L = {a ^ {n} b ^ {n} c ^ {n} | ngeq 1}.}$

Přidružené slovo uživatele ${displaystyle a ^ {n} b ^ {n} c ^ {n}}$je${displaystyle Aw (a ^ {n} b ^ {n} c ^ {n}) = m_ {1} m_ {2} ^ {n-2} m_ {3}, forall ngeq 2}$ a ${displaystyle Aw (abc) = m_ {0}}$.

Vlastnosti

Nechat ${displaystyle {ce {MAT ^ {lambda}}}}$ být třídou jazyků produkovaných maticovými gramatikami a ROHOŽ třída jazyků produkovaných ${displaystyle lambda}$- maticové gramatiky zdarma.

• Triviálně, ROHOŽ je součástí ${displaystyle {ce {MAT ^ {lambda}}}}$.
• Všechno bezkontextové jazyky jsou v ROHOŽa všechny jazyky v ${displaystyle {ce {MAT ^ {lambda}}}}$ jsou rekurzivně spočetné.
• ROHOŽ je uzavřen pod svaz, zřetězení, průsečík s běžnými jazyky a obměnami.
• Všechny jazyky v ROHOŽ mohou být vyrobeny a kontextová gramatika.
• Existuje kontextový jazyk, který nepatří ${displaystyle {ce {MAT ^ {lambda}}}}$ ^[2].
• Každý jazyk produkovaný maticovou gramatikou s pouze jedním koncovým symbolem je regulární.

Otevřené problémy

Není známo, zda v jazyce existují jazyky ${displaystyle {ce {MAT ^ {lambda}}}}$ které nejsou v ROHOŽ, a není ani známo, zda ${displaystyle {ce {MAT ^ {lambda}}}}$ obsahuje jazyky, které nejsou kontextově citlivé ^[3].

Reference

Poznámky pod čarou

• ^ Ábrahám, S. Některé otázky teorie jazyků. International Conference on Computational Linguistic, 1965. pp 1–11. [4]
• ^ Gheorghe Păun, Membrane Computing: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2002. str. 30–32