Matriisikielioppi

Matriisikielioppi on muodollinen kielioppi , jossa päättelysäännöt on ryhmitelty äärellisiin sarjoihin. Päättelysääntöjä ei voi soveltaa yksittäin, vaan vain peräkkäin. Tätä sekvenssiä sovellettaessa korvaus tehdään sekvenssin jokaisen säännön mukaisesti ensimmäisestä viimeiseen. Sekvenssejä kutsutaan matriiseiksi . Matriisikielioppi on yhteydettömän kieliopin laajennus .

Muodollinen määritelmä

Matriisikielioppi on järjestetty neliö

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

missä

$V_{N}$ on äärellinen joukko ei-terminaalisia symboleja
$V_{T}$ on äärellinen joukko päätemerkkejä
$X_{0}\in V_{N}$ - aloitussymboli
$M$ on rajallinen joukko järjestetyn parin ei-tyhjiä sekvenssejä

{\näyttötyyli (P,Q),\quad P\in W(V)V_{N}W(V),\quad Q\in W(V),\quad V=V_{N}\cup V_{T }.}

Pareja kutsutaan päättelysäännöiksi, ja ne kirjoitetaan muodossa . Sekvenssejä kutsutaan matriiseiksi ja ne kirjoitetaan muodossa $P\to Q$

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

Antaa olla joukko kaikki päättelysäännöt matriisikieliopin matriiseissa . Tällöin kielioppi on tyyppinen kielioppi , ei- lyhentävä , lineaarinen , -free , yhteydetön tai kontekstiherkkä , jos ja vain jos kielioppi sisältää tämän ominaisuuden. $F$ $m$ $G$ $G$ ${\näyttötyyli i,i=0,1,2,3}$ $\lambda$ $G_{1}=(V_{N},V_{T},X_{0},F)$

Matriisikieliopissa määritellään binäärirelaatio , jota myös merkitään . Jokaiselle , pätee jos ja vain, jos on kokonaisluku siten, että on sanoja $G$ $\Rightarrow _{G}$ $\Nuoli oikealle$ $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}

yli sarjan V ja

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

Jos määritellyt ehdot täyttyvät, sen sanotaan myös täyttyvän spesifikaatiolla . $P\Rightarrow Q$ ${\näyttötyyli (m,R_{1})}$

Antaa olla reflektiivinen transitiivinen sulkeminen suhteen . Sitten matriisikieliopin luoma kieli määritellään seuraavasti: $\Rightarrow ^{*}$ $\Nuoli oikealle$ $G$

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

Esimerkki

Harkitse matriisikielioppia

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

missä on seuraavien matriisien kokonaismäärä: $M$

$[S\rightarrow XY],\quad [X\rightarrow aXb,Y\rightarrow cY],\quad [X\rightarrow ab,Y\rightarrow c]$

Nämä matriisit, jotka sisältävät vain yhteydettömiä sääntöjä, synnyttävät kontekstiherkän kielen

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

Tämä esimerkki löytyy sivuilta 8 ja 9 [1] .

Muistiinpanot

↑ Ábrahám, S. Joitakin kieliteorian kysymyksiä. International Conference on Computational Linguistic, 1965. s. 1–11. [2] (linkki ei ole käytettävissä 13.5.2013 lähtien [3454 päivää] - historia )