stringa

stringa

stringa sequenza finita di caratteri cioè di simboli appartenenti all’alfabeto di un dato linguaggio formale. Si consideri, per esempio, l’alfabeto costituito unicamente dai due simboli 0 e 1. In questo caso le stringhe o parole dell’alfabeto sono tutte le sequenze finite di 0 e 1 come per esempio 1000011101. In generale, una stringa può contenere simboli qualsiasi di un linguaggio formale come numeri, lettere, segni di interpunzione, parentesi, simboli logici (connettivi e quantificatori), simboli predicativi ecc. Per esempio, la scrittura ∀x∃y(x = y) è una stringa di simboli appartenenti al linguaggio logico dei → predicati. I linguaggi formali comprendono delle regole sintattiche che permettono di identificare, fra tutte le stringhe possibili, quelle significative dette → formule ben formate: per esempio, utilizzando i simboli dell’aritmetica possono essere costruite stringhe come 2+1=3 oppure +=3 o ancora =+4−00; fra esse solo la prima è sintatticamente corretta cioè rispetta le usuali regole per la costruzione di formule aritmetiche. Una qualsiasi sequenza s di caratteri contenuti in una stringa α e consecutivi viene detta sottostringa di α: la stringa 10011 è una sottostringa di 0101100111010. Nell’insieme delle stringhe costruite su un dato alfabeto è definita l’operazione di → concatenazione: date due stringhe α e β, la stringa γ = αβ, costruita giustapponendo ai simboli di α quelli di β, è la stringa ottenuta per concatenazione delle prime due. A ogni stringa è associato un numero naturale, detto lunghezza della stringa che esprime il numero dei caratteri che la compongono: assegnare una lunghezza alle stringhe di un alfabeto A vuol dire stabilire una funzione tra l’insieme di tali stringhe, generalmente indicato con A⁺, e l’insieme N. Ha senso allora considerare anche la stringa di “lunghezza 0”, cioè non contenente alcun carattere (o, detto in modo equivalente, la stringa costituita dal solo carattere vuoto). Tale stringa è detta stringa vuota e, quando si vuole precisare che essa deve considerarsi inclusa nell’insieme di tutte le stringhe costruite a partire dall’alfabeto A, si indica tale insieme con A*.

La stringa vuota è un artificio che permette di interpretare anche il vuoto che separa due stringhe come un particolare carattere. Inoltre la stringa vuota può essere considerata come elemento neutro rispetto all’operazione di concatenazione fra stringhe. Infatti concatenando una qualsiasi stringa α con la stringa vuota si ottiene ancora la stringa α.