Stringa (linguaggi formali)

Nella teoria dei linguaggi formali, una stringa è 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 bit, 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 routine di sistemi software. In linea di principio gli strumenti del secondo genere si possono considerare implementazioni dei primi.

Trattamento formale

Dato un insieme finito non-vuoto $\Sigma$, chiamato alfabeto, composto da caratteri o simboli è possibile definire una stringa (o parola) sull'alfabeto $\Sigma$ come disposizione (o ennupla) finita dei caratteri di $\Sigma$.

È possibile definire la lunghezza di una stringa, $\left|w\right|$ come il numero di caratteri presenti nella stringa. La stringa di lunghezza 0 prende il nome di stringa vuota o stringa nulla e viene indicata con $\varepsilon$ o $\lambda$.

Per esempio, preso l'alfabeto binario $\Sigma =\left\{0,1\right\}$, alcune delle parole che possono essere generate a partire da $\Sigma$ sono le stringhe $\left\{\varepsilon ,0,1,00,01,10,11,000,001,010,011,100,\cdots \right\}$.

Possiamo definire l'operazione elevamento a potenza di un alfabeto, $\Sigma ^{k}$, come l'insieme di stringhe di lunghezza k sull'alfabeto, ponendo $\Sigma ^{0}=\varepsilon$.

L'insieme di tutte le parole sull'alfabeto $\Sigma$ è indicato con $\Sigma ^{*}$. Data l'esistenza di una corrispondenza biunivoca tra la tupla $\left(a_{1},a_{2},\cdots ,a_{n}\right)$ e la stringa $a_{1}a_{2}\cdots a_{n}$, è possibile definire la star chiusura come l'insieme infinito $\Sigma ^{*}=\bigcup _{n\in \mathbb {N} }\Sigma ^{n}$.

È possibile definire l'insieme delle parole di lunghezza sull'alfabeto $\Sigma$, la cross chiusura, come $\Sigma ^{+}=\Sigma ^{*}\setminus \Sigma ^{0}$.

È inoltre possibile definire un'operazione binaria denominata concatenazione di stringhe. Siano s e t appartenenti rispettivamente agli alfabeti $\Sigma ^{\prime }$ e $\Sigma ^{\prime \prime }$. La concatenazione delle due stringhe, indicata come st, è definita come la stringa di lunghezza $\left|s\right|+\left|t\right|$ appartenente a $\Sigma ^{\prime }\cup \Sigma ^{\prime \prime }$ , che presenta ordinatamente i caratteri di s seguiti dai simboli di t.

Ad esempio se $s={\mbox{topo}}$ e $t={\mbox{ragno}}$ allora $st={\mbox{toporagno}}$ e $ts={\mbox{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 $\Sigma ^{*}$ costituisce un monoide rispetto alla concatenazione di stringhe. $\Sigma ^{*}$ è il monoide libero generato da $\Sigma$, mentre $\Sigma ^{+}$ è il relativo semigruppo libero.

Sempre da un punto di vista algebrico, dato che la lunghezza è un numero naturale, è possibile dire che la funzione lunghezza definisce un omomorfismo da $\Sigma ^{*}$ in $\mathbb {N}$.

Una stringa s si dice sottostringa o fattore di t se esistono due stringhe u e v tali che $t=usv$. Se $u=\varepsilon$ o $v=\varepsilon$ si parla di prefisso o suffisso della stringa t. La relazione "è una sottostringa di" definisce una relazione d'ordine su $\Sigma ^{*}$, il cui minimo risulta la stringa vuota.

Se l'alfabeto $\Sigma ^{*}$ è ben ordinato, il cosiddetto ordine lessicografico costituisce un altro ordinamento totale su $\Sigma ^{*}$ di frequente utilizzo per le applicazioni informatiche.

Un insieme di stringhe su $\Sigma$ (cioè un sottoinsieme di $\Sigma ^{*}$) è anche detto linguaggio formale su $\Sigma$. Nonostante l'alfabeto $\Sigma$ sia finito e non vuoto e le stringhe siano di lunghezza finita, i linguaggi formali possono avere cardinalità infinita o nulla. Esempi di linguaggi formali sono forniti dalle espressioni regolari e dalle grammatiche formali.

Bibliografia

• (EN) John E. Hopcroft, Rajeev Motwani; Jeffrey D. Ullman, Strings, in Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 15 luglio 2006, ISBN 978-0-321-46225-1.
• (EN) Martin Davis, Ron Sigal; Elaine J. Weyuker, Alphabets and Strings, in Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Morgan Kaufmann, 17 febbraio 1994, ISBN 978-0-12-206382-4.

Voci correlate

• Stringa (informatica)
• Alfabeto (teoria dei linguaggi formali)
• Linguaggio formale