Maticová gramatika

Maticová gramatika je formální gramatika , ve které jsou odvozená pravidla seskupena do konečných sekvencí. Odvozovací pravidla nelze aplikovat jednotlivě, ale pouze postupně. Při použití této sekvence se substituce provádí podle každého pravidla v sekvenci, od prvního do posledního. Posloupnosti se nazývají matice . Maticová gramatika je rozšířením bezkontextové gramatiky .

Formální definice

Maticová gramatika je uspořádaná čtveřice

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

kde

$V_{N}$ je konečná množina neterminálních symbolů
$V_{T}$ je konečná množina terminálních symbolů
$X_{0}\in V_{N}$ - startovací symbol
$M$ je konečná množina neprázdných posloupností uspořádaných dvojic

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

Páry se nazývají inferenční pravidla a jsou zapsány jako . Sekvence se nazývají matice a zapisují se jako $P\to Q$

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

Nechť je množina všech odvozovacích pravidel v maticích maticové gramatiky . Pak je gramatika typ gramatika , nezkracující se , lineární , -free , bezkontextová nebo kontextová, pokud a pouze tehdy, má-li gramatika tuto vlastnost. $F$ $m$ $G$ $G$ $i,i=0,1,2,3$ $\lambda$ $G_{1}=(V_{N},V_{T},X_{0},F)$

Pro maticovou gramatiku je definován binární vztah označovaný také . For any , platí tehdy a jen tehdy, když existuje celé číslo takové, že existují slova $G$ $\Rightarrow _{G}$ $\Šipka doprava$ $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}

přes množinu V a

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

Pokud jsou splněny stanovené podmínky, říká se, že je splněna i specifikace . $P\Rightarrow Q$ $(m,R_{1})$

Nechť je reflexivní tranzitivní uzavření vztahu . Potom je jazyk generovaný maticovou gramatikou definován takto: $\Rightarrow ^{*}$ $\Šipka doprava$ $G$

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

Příklad

Zvažte maticovou gramatiku

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

kde je součet následujících matic: $M$

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

Tyto matice obsahující pouze bezkontextová pravidla dávají vzniknout kontextově citlivému jazyku

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

Tento příklad lze nalézt na stranách 8 a 9 [1] .

Poznámky

↑ Ábrahám, S. Některé otázky teorie jazyka. International Conference on Computational Linguistic, 1965. s. 1–11. [2] (odkaz nedostupný od 13-05-2013 [3454 dní] - historie )