Matris grammatik

En matrisgrammatik är en formell grammatik där slutledningsregler grupperas i finita sekvenser. Slutledningsregler kan inte tillämpas individuellt, utan endast i följd. Vid tillämpning av denna sekvens görs substitutionen enligt varje regel i sekvensen, från första till sista. Sekvenser kallas matriser . Matrisgrammatik är en förlängning av kontextfri grammatik .

Formell definition

Matrix grammatik är en ordnad quad

G=(V_{N},V_{T},X_{0},M).

var

$V_{N}$ är en ändlig uppsättning icke-terminala symboler
$V_{T}$ är en ändlig uppsättning terminalsymboler
$X_{0}\in V_{N}$ - startsymbol
$M$ är en ändlig uppsättning av icke-tomma sekvenser av ordnade par

(P,Q),\quad P\in W(V)V_{N}W(V),\quad Q\in W(V),\quad V=V_{N}\cup V_{T }.

Paren kallas slutledningsregler och skrivs som . Sekvenser kallas matriser och skrivs som $P\to Q$

m=[P_{1}\to Q_{1},\ldots ,P_{r}\to Q_{r}].

Låta vara uppsättningen av alla slutledningsregler i matrisens grammatik . Då är en grammatik en typ grammatik , icke- förkortande , linjär , -fri , kontextfri eller kontextkänslig om och bara om grammatiken har denna egenskap. $F$ $m$ $G$ $G$ $i,i=0,1,2,3$ $\lambda$ $G_{1}=(V_{N},V_{T},X_{0},F)$

För en matrisgrammatik definieras en binär relation , även betecknad med . För alla , gäller om och endast om det finns ett heltal så att det finns ord $G$ $\Rightarrow _{G}$ $\Höger pil$ $P,Q\in W(V)$ $P\Rightarrow Q$ $r\geq 1$

\alpha _{1},,\ldots ,\alpha _{r+1},\quad P_{1},\ldots ,P_{r},\quad R_{1},\ldots ,R_{ r},\quad ,R^{1},\ldots ,R^{r}

över uppsättningen V och

$\alpha _{i}=P$ och $\alpha _{r+1}=Q$
$m\in G$
${\displaystyle \alpha _{i}=R_{i}P_{i}R^{i))$ och $\alpha _{i+1}=R_{i}Q_{i}R^{i}.$

Om de angivna villkoren är uppfyllda sägs det också vara uppfyllt med specifikation . $P\Rightarrow Q$ $(m,R_{1})$

Låt vara en reflexiv transitiv stängning av relationen . Sedan definieras språket som genereras av matrisgrammatiken enligt följande: $\Rightarrow ^{*}$ $\Höger pil$ $G$

L(G)=\{P\in W(V_{T})|X_{0}\Rightarrow ^{*}P\}.

Exempel

Tänk på matrisgrammatik

$G=(\{S,A,B\},\{a,b,c\},S,M)$

var är summan av följande matriser: $M$

$[S\högerpil XY],\quad [X\högerpil aXb,Y\högerpil cY],\quad [X\högerpil ab,Y\högerpil c]$

Dessa matriser, som endast innehåller kontextfria regler, ger upphov till ett sammanhangskänsligt språk

$L=\{a^{n}b^{n}c^{n}|n\geq 1\}.$

Detta exempel finns på sidorna 8 och 9 [1] .

Anteckningar

↑ Ábrahám, S. Några frågor om språkteori. International Conference on Computational Linguistic, 1965. s 1–11. [2] (otillgänglig länk sedan 2013-05-13 [3454 dagar] - historik )