Un alfabeto \Sigma è un insieme finito di elementi detti simboli: \Sigma = \{ a_1, a_2, \dots , a_n \} . Una parola (o stringa) sull’alfabeto \Sigma è una sequenza finita di simboli appartenenti a \Sigma . Ad esempio: “aababbab” e “bbababb” sono due parole originate dall’alfabeto \{ a, b \} .

Un particolare simbolo che può appartenere (o non appartenere) ad un certo alfabeto è la parola vuota. La parola vuota viene indicata con il simbolo: \varepsilon (epsilon).

Data una parola w (definita dalla concatenazione di più simboli appartenenti all’alfabeto \Sigma ), indichiamo con l(w) oppure con |w| la lunghezza di w . La lunghezza della parola w rappresenta il numero di simboli (distinti per posizione) che compongono la parola vuota.

Ad esempio:

  • Consideriamo la generica parola w vista in precedenza ( w = ``aababbab'' ) essa è composta da 8 simboli distinti per posizione (ad esempio: l(w)=8 );
  • La parola vuota è l’unica parola composta da zero simboli, quindi di lunghezza zero ( l(\varepsilon)=0 ).

Dato un alfabeto \Sigma , l’insieme di tutte le parole che si possono ottenere da \Sigma viene indicato con \Sigma^* , mentre l’insieme di tutte le parole che si possono ottenere da \Sigma senza la parola vuota ( \varepsilon ) viene indicato con \Sigma^+ .

Date due parole x = x_1, x_2, \dots, x_n e y = y_1, y_2, \dots , y_m si dice prodotto di giustapposizione di x e y (e si indica con x \cdot y ) la parola z = x_1, x_2, \dots , x_n, y_1, y_2, .., y_m . La parola z è quindi il risultato della concatenazione delle parole x e y . Ovviamente la lunghezza della parola z corrisponde alla somma tra la lunghezza di x e la lunghezza di y ( l(z)=l(x)+l(y) ).

Il prodotto di giustapposizione è un’operazione binaria su \Sigma^* . Un’operazione binaria è una funzione con arietà due (che richiede due argomenti in input) e che restituisce in output un terzo elemento appartenente all’insieme. Il prodotto di giustapposizione gode della proprietà associativa e in cui la parola vuota ( \varepsilon ) è l’elemento neutro.
In sintesi:
(x \cdot y) \cdot z = x \cdot (y \cdot z)
x \cdot \varepsilon = \varepsilon \cdot x = x

Grazie a queste due proprietà l’insieme \Sigma^* con l’operazione di giustapposizione e l’elemento neutro forma un monoide. Un monoide è una struttura algebrica dotata dell’operazione binaria associativa e dell’elemento neutro. La terna (\Sigma^*, \cdot, \varepsilon) è detta monoide libero generato da \Sigma .

Date le parole x, y diremo che x è prefisso di y se y = x \cdot z per qualche z , x è suffisso di y se y = z \cdot x per qualche z , infine x è fattore se y = z \cdot x \cdot w per qualche z e w .