Prepisivanje stringa

Sustav prepisivanja stringa je supstitucijski sustav korišten za transformiranje stringa prema specificiranim pravilima prepisivanja.

Ekvivalencija osnovnih sustava prepisivanja stringa

Određeni osnovni oblici sustava prepisivanja stringa su u biti istovjetni sustavima prepisivanja termina. Pretpostavimo da imamo stringove nad abecedom A, i da je dan skup pravila tranformiranja nad podstringovima oblika

$x_0{x}_1\cdots x_n\to y_0{y}_1\cdots y_m,x_i,y_i\in A$

naznačujući da bilo koji podstring x₀x₁...x_n valja zamijeniti s y₀y₁...y_m.

Takav se sustav može reformulirati u sustav prepisivanja termina - transformacijska pravila sad postaju

$x_0(x_1(\cdots (x_n(x)))\cdots )\to y_0(y_1(\cdots (y_m(x))\cdots ),$

gdje svako x_i i y_i čine funkcijske simbole u sustavu prepisivanja termina.

Stringovi u ovom sustavu prepisivanja termina su tad temeljni termini.

Primjeri

Primjeri računskih modela zasnovanih na determinističkom prepisivanju stringa uključuju Markovljev algoritam, Postov kanonski sustav (npr. sustav oznaka), niz formalnih gramatika, te L-sustave (potonji se ponajviše koriste za stvaranje određenih skupova fraktala kao što su Cantorov skup i Mengerova spužva).

Vidjeti također

• Formalna gramatika
• L-sustav
• Markovljev algoritam
• Semi-Thue sustav
• Sustav oznake