Otvori glavni izbornik

Prepisivanje stringa

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

Ekvivalencija osnovnih sustava prepisivanja stringaUredi

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

 

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

 

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

Stringovi u ovom sustavu prepisivanja termina su tad temeljni termini.

PrimjeriUredi

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đerUredi


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