Un alfabeto $\Sigma$ è un insieme finito e non vuoto di simboli, dove un simbolo è un “oggetto qualunque”: può essere un carattere, una sequenza di caratteri (come ad esempio una parola chiave di un linguaggio di programmazione), ecc…
Una stringa (o parola) su $\Sigma$ è una qualunque sequenza finita di simboli di $\Sigma$ (si considerano solo sequenza finite perchè quelle infinite non potrebbero essere analizzate, trattate per intero, dunque risulterebbe impossibile assegnarvi un significato). In particolare, è una stringa anche la sequenza vuota, composta da zero simboli di $\Sigma$, che prende il nome di stringa vuota e viene indicata con $\epsilon$.
Per convenzione, si indicheranno
i simboli di $\Sigma$ con le lettere latine minuscole della parte iniziale dell’alfabeto, eventualmente indiciate:
$$ a, b, c, \dots, a_0, a_1, \dots, a_n, \dots $$
(ma, in alcuni esempi, si indicheranno invece i simboli con delle parole aventi un significato intuitivo nel contesto di tali esempi);
le stringhe su $\Sigma$ con le lettere latine minuscole della parte finale dell’alfabeto, oppure con le lettere greche minuscole, eventualmente indiciate:
$$ u, v, w, x, y, z, \alpha, \beta, \gamma, \delta, \dots, \alpha_0, \alpha_1, \dots, \alpha_n, \dots $$
Se $a_1,\dots, a_n\in\Sigma$ (con $n\geq 0$), si scrive
$$ w=a_1\dots a_n $$
per indicare la stringa costituita da $n$ simboli di $\Sigma$ che ha $a_i$ come $i$-esimo simbolo della sequenza (per $i=1,\dots , n$. Come caso particolare, se $n=0$ si ha $w=\epsilon$).
Data una stringa $w$, si indica con $|w|$ la sua lunghezza, definita come il numero di occorrenze di simboli di $\Sigma$ in $w$. La lunghezza della stringa vuota è $|\epsilon|=0$.
Sia $\Sigma=\{0, 1\}$. I seguenti sono alcuni esempi di stringhe su $\Sigma$, con le rispettive lunghezze:
Date due stringhe $\alpha$ e $\beta$ su $\Sigma$, la concatenazione di $\alpha$ con $\beta$, indicata con $\alpha\beta$, è la stringa costituita dai simboli di $\alpha$ seguiti dai simboli di $\beta$. Ad esempio, considerando ancora l’alfabeto $\Sigma=\{0, 1\}$, date $\alpha=01$ e $\beta=11$ si ha $\alpha\beta=0111$.
Formalmente, la concatenazione è un operatore binario sulle stringhe, in quanto “prende” due stringhe e produce come risultato una nuova stringa. Si osserva che $\epsilon$ è l’elemento neutro di tale operatore: per ogni stringa $\alpha, \epsilon\alpha = \alpha\epsilon=\alpha$.
Siano $\alpha$ e $\beta$ due stringhe su $\Sigma$.