Prepisovalni sistemi

Skoči na: navigacija, iskanje

Prepisovalni sistem je definiran kot dvojica

$G=\langle \Sigma, P \rangle$

kjer je $Σ$ abeceda, P pa množica produkcij oz. prepisovalnih pravil, ki povedo kako se določen niz preslika v nov niz.

$P \subset \Sigma^*\times\Sigma^*$

Produkcije oz. prepisovalna pravila ponavadi zapišemo kot

$\displaystyle p = [w_1 \rightarrow w_2] \in P$

Definiramo tudi relacijo izpeljave, ki pove, kako prepisovalni sistem nad danim nizom uporabi neko produkcijo p.

$\Longrightarrow^p_G\ = \{\langle a w_1 b, a w_2 b\rangle | a,b\in\Sigma^* \}$