Prepisivanje stringa

Izvor: Wikipedija

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

[uredi] 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_0x_1\cdots x_n \rightarrow y_0y_1\cdots y_m,\quad x_i, y_i \in A

naznačujući da bilo koji podstring x0x1...xn valja zamijeniti sa y0y1...ym.

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

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

gdje svako xi i yi čine funkcijske simbole u sustavu prepisivanja termina.

Stringovi u ovom sustavu prepisivanja termina su tad temeljni termini.

[uredi] 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).

[uredi] Vidjeti također


Nedovršeni članak Prepisivanje stringa koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.

Drugi jezici