Șir (limbi formale)

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

În teoria limbajului formal , un șir este o secvență alcătuită dintr-un număr de obiecte care se așteaptă să fie supuse prelucrării, cum ar fi analize, compoziții și transformări în alte șiruri sau structuri discrete, cum ar fi grafice sau configurații numerice, fără a modifica obiectele componente.

Obiectele constitutive pot fi simple (cum ar fi biți, caractere sau simboluri) sau compuse, dar pot fi tratate ca și cum ar fi simple (cum ar fi cuvinte, expresii, fragmente de text sau semne ale obiectelor compozite, dar care nu trebuie analizate sau descompuse) .

Din punct de vedere al constituției, se disting în primul rând șirurile obiectelor simple: șiruri de biți ( șiruri binare ), șiruri compuse din caractere ( șiruri literale ), șiruri de simboluri ( șiruri simbolice ). Șirurile de obiecte compozite includ șiruri formate din unități lexicale (numite și jetoane ), fragmente de text (cum ar fi titluri de paragraf sau citații bibliografice) și șiruri care reprezintă molecule cu o structură filamentoasă generală, cum ar fi cele care reprezintă o proteină sau o structură de ADN .

Printre instrumentele care pot supune șirurile la procesare, se disting cele formale, cum ar fi automatele , mașinile Turing , gramaticile formale sau alte sisteme de rescriere, și cele mai concrete constând din programe sau rutine ale sistemelor software. În principiu, instrumentele de al doilea tip pot fi considerate ca implementări ale primului.

Tratament formal

Dat fiind un set finit non-gol , numitalfabet , compus din caractere sau simboluri puteți defini un șir (sau un cuvânt ) pe alfabet ca aranjament finit (sau tuplu ) al caracterelor de [1] [2] .

Puteți defini lungimea unui șir, ca număr de caractere din șir. Șirul de lungime 0 se numește șir gol sau șir nul și este indicat cu sau [1] .

De exemplu, am luat alfabetul binar , unele dintre cuvintele care pot fi generate din sunt corzile .

Putem defini operația de ridicare la puterea unui alfabet, , ca set de șiruri de lungime k pe alfabet, prin plasare .

Setul tuturor cuvintelor de pe alfabet este indicat cu . Având în vedere existența unei corespondențe unu-la-unu între tuplu și șirul , este posibil să se definească steaua de închidere ca mulțimea infinită .

Puteți defini setul de cuvinte de lungime pe alfabet , crucea de închidere , ca .

De asemenea, este posibil să se definească o operație binară numită concatenare de șiruri [1] . Să aparțină s și t respectiv alfabetelor Și . Concatenarea celor două șiruri, notate ca st , este definită ca șirul de lungime aparținând , care prezintă ordonat caracterele lui s urmate de simbolurile lui t .

De exemplu dacă Și asa de Și .

Concatenarea șirurilor este o operație asociativă, dar nu o comutativă [1] . În ceea ce privește concatenarea, șirul gol este elementul neutru . În termeni algebrici , mulțimea constituie un monoid în ceea ce privește concatenarea șirurilor [1] . este monoidul liber generat de , in timp ce este semigrupul relativ liber.

Din nou din punct de vedere algebric, având în vedere că lungimea este un număr natural , este posibil să spunem că funcția lungime definește un omomorfism din în .

Un șir de caractere s se numește subșir sau factor de t în cazul în care există două șiruri u și v astfel încât . De sine sau vorbim de prefix sau sufix al șirului t . Relația "este un șir de" definește o relație de ordine pe , al cărui minim este șirul gol.

Dacă alfabetul este bine ordonat , așa-numita ordine lexicografică constituie o altă ordonare totală pe frecvent utilizat pentru aplicații informatice.

Un set de corzi pe (adică un subset de ) se mai numește limbajul formal pe . În ciuda alfabetului atât finite, cât și non-goale, iar șirurile sunt de lungime finită, limbajele formale pot avea cardinalitate infinită sau nulă . Exemple de limbaje formale sunt oferite de expresii regulate și gramatici formale .

Notă

  1. ^ a b c d e Limbajele și gramaticile formale ale lui Chomsky ( DOC ), pe dis.uniroma1.it , 4-7. Accesat la 19 mai 2017 ( arhivat la 2 iunie 2010) .
  2. ^ Giacomo Piscitelli, Limbaje formale și compilatoare ( PDF ), pe www-ictserv.poliba.it , p. 4. Adus la 17 mai 2017 (arhivat din original la 16 iunie 2015) .

Bibliografie

Elemente conexe