Matrix grammatik

En matrixgrammatik er en formel grammatik , hvor inferensregler er grupperet i endelige sekvenser. Inferensregler kan ikke anvendes individuelt, men kun i rækkefølge. Når du anvender denne sekvens, foretages substitutionen i henhold til hver regel i sekvensen, fra først til sidst. Sekvenser kaldes matricer . Matrix grammatik er en udvidelse af kontekstfri grammatik .

Formel definition

Matrix grammatik er en ordnet quad

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

hvor

$V_{N}$ er et begrænset sæt af ikke-terminale symboler
$V_{T}$ er et begrænset sæt terminalsymboler
$X_{0}\in V_{N}$ - startkarakter
$M$ er et begrænset sæt af ikke-tomme sekvenser af ordnede par

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

Parrene kaldes slutningsregler og skrives som . Sekvenser kaldes matricer og skrives som $P\to Q$

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

Lade være mængden af alle inferens regler i matricer af matrix grammatik . Så er en grammatik en type grammatik , ikke- afkortende , lineær , -fri , kontekstfri eller kontekstafhængig, hvis og kun hvis grammatikken har denne egenskab. $F$ $m$ $G$ $G$ $i,i=0,1,2,3$ $\lambda$ $G_{1}=(V_{N},V_{T},X_{0},F)$

For en matrixgrammatik er en binær relation defineret , også betegnet med . For enhver , gælder hvis og kun hvis der er et heltal , således at der er ord $G$ $\Rightarrow _{G}$ $\Højre 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}

over sættet V og

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

Hvis de angivne betingelser er opfyldt, siges det også at være opfyldt med specifikation . $P\Rightarrow Q$ $(m,R_{1})$

Lad være en refleksiv transitiv lukning af forholdet . Derefter er det sprog, der genereres af matrixgrammatikken , defineret som følger: $\Rightarrow ^{*}$ $\Højre pil$ $G$

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

Eksempel

Overvej matrix grammatik

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

hvor er helheden af følgende matricer: $M$

$[S\højrepil XY],\quad [X\højrepil aXb,Y\højrepil cY],\quad [X\højrepil ab,Y\højrepil c]$

Disse matricer, der kun indeholder kontekstfrie regler, giver anledning til et kontekstfølsomt sprog

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

Dette eksempel kan findes på side 8 og 9 [1] .

Noter

↑ Ábrahám, S. Nogle spørgsmål om sprogteori. International Conference on Computational Linguistic, 1965. s 1-11. [2] (utilgængeligt link siden 13-05-2013 [3454 dage] - historie )