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
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.
[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
- Formalna gramatika
- L-sustav
- Markovljev algoritam
- Semi-Thue sustav
- Sustav oznake
Nedovršeni članak Prepisivanje stringa koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.