Stringa (formale)
Da Wikipedia, l'enciclopedia libera.
In varie discipline della matematica e dell'informatica, per stringa si intende una sequenza composta da un certo numero di oggetti che ci si aspetta venga sottoposta ad elaborazioni come analisi, composizioni e trasformazioni in altre stringhe o strutture discrete come grafi o configurazioni numeriche, senza modificare gli oggetti componenti.
Gli oggetti costitutivi possono essere semplici (come bits, caratteri o simboli) o compositi, ma da trattare come se fossero semplici (come parole, espressioni, frammenti di testo o contrassegni di oggetti compositi ma che non si vogliono analizzare o decomporre).
Dal punto di vista della costituzione si distinguono innanzi tutto le stringhe di oggetti semplici: stringhe di bit (stringhe binarie), stringhe composte da caratteri (stringhe letterali), stringhe di simboli (stringhe simboliche). Tra le stringhe di oggetti compositi si collocano le stringhe composte da unità lessicali (dette anche token), i frammenti di testo (come i titoli dei paragrafi o le citazioni bibliografiche) e le stringhe che rappresentano molecole dotate di struttura complessiva filamentosa, come quelle che rappresentano una proteina o una struttura di DNA.
Tra gli strumenti che possono sottoporre le stringhe ad elaborazioni si distinguono quelli formali, come gli automi, le macchine di Turing, le grammatiche formali o altri sistemi di riscrittura e quelli più concreti costituiti da programmi o routines di sistemi software. In linea di principio gli strumenti del secondo genere si possono considerare implementazioni dei primi.
[modifica] Trattamento formale
Si inizia con un insieme finito non-vuoto Σ chiamato alfabeto. Gli elementi di questo alfabeto sono chiamati caratteri. Una stringa (o parola) in Σ è una qualsiasi sequenza finita di caratteri di Σ.
Una stringa di importanza particolare è la sequenza composta da nessun carattere, chiamata stringa vuota. La stringa vuota è spesso indicata con ε o λ. Le sequenze infinite non sono considerate stringhe.
Per esempio, se Σ = {0, 1}, le stringhe in Σ sono nella forma
- ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …
L'insieme di tutte le stringhe in Σ (le "parole su Σ") è indicato come Σ*. Identificando biiettivamente la sequenza a1a2...an con l'n-upla (a1,a2,...,an) allora l'insieme Σ* è dato da
,
dove Σ0: = {ε}. Alcune volte è opportuno invece restringersi all'insieme delle parole di lunghezza positiva, diverse da quella vuota: tale insieme è denotato con Σ+ ed è Σ* \ Σ0.
Si può definire un'operazione binaria in Σ* chiamata concatenazione di stringhe. Se s e t sono due stringhe, la loro concatenazione, indicata come st, è definita come la sequenza di caratteri in s seguita dalla sequenza di caratteri in t.
Per esempio, se s = topo e t = ragno allora st = toporagno e ts = ragnotopo.
La concatenazione di stringhe è un'operazione associativa, ma non-commutativa. Rispetto alla concatenazione, la stringa vuota è l'elemento neutro. In termini algebrici, l'insieme Σ* costituisce un monoide rispetto alla concatenazione di stringhe. In effetti, Σ* è il monoide libero generato da Σ, mentre Σ+ il relativo semigruppo libero.
La lunghezza di una stringa è data dal numero di caratteri che la compongono, e può essere un qualsiasi numero naturale. La lunghezza della stringa vuota è 0. Da un punto di vista algebrico, la funzione lunghezza definisce un omomorfismo da Σ* a N (l'insieme dei numeri interi non negativi con l'addizione).
Una stringa s si dice sottostringa o fattore di t se esistono due stringhe u e v tali che t = usv. Si noti che u e/o v possono essere vuote. La relazione "è una sottostringa di" definisce una relazione d'ordine su Σ*, il cui minimo risulta la stringa vuota.
Se l'alfabeto Σ è ben ordinato, il cosiddetto ordine lessicografico costituisce un altro ordinamento totale su Σ*, di frequente utilizzo per le applicazioni informatiche.
Un insieme di stringhe su Σ (cioè un sottoinsieme di Σ*) è anche detto linguaggio formale su Σ. Si noti che nonostante l'alfabeto sia finito ed ogni stringa abbia lunghezza finita, nulla vieta che un linguaggio formale contenga un numero infinito di stringhe. In effetti, Σ* stesso è sempre un linguaggio infinito. Esempi notevoli di linguaggi formali sono forniti dalle espressioni regolari e dalle grammatiche formali.
