Definizioni Introduttive

Aflabeto: insieme finito e non vuoto di simboli. Si usa Σ quando ci si riferisce a questo inseieme.

Stringa su Σ: sequenza finita di simboli di Σ.

Esempio

se Σ={a,b}

le stringhe che posso comporre su Σ sono: a,b,aa,ab,abb,ababa,ecc

 

Lunghezza di una stringa: la lunghezza di una stringa è il numero di caratteri la compongono. Per indicare la lunghezza della stringa si usa il | (modulo).

Esempio

Σ={a,b}

w (stringa su Σ) = abba

|w| = 4