parola

parola

parola in un linguaggio formale, sinonimo di → stringa finita; è una sequenza finita di caratteri dell’alfabeto utilizzato dal linguaggio, giustapposti l’uno all’altro. Se, per esempio, l’alfabeto del linguaggio è costituito da due soli caratteri, 0 e 1, ogni sequenza finita di 0 e 1, quale 01001101, è una parola del linguaggio. La concatenazione di due parole a e b è ancora una parola ottenuta come giustapposizione, nell’ordine, di a e b. Per esempio, se a = 1011 e b = 1001, allora la loro concatenazione ab è la parola 10111001. Il numero di caratteri che compongono una parola è detto lunghezza della parola stessa. Attribuire la lunghezza a una parola di un dato alfabeto A vuol dire, quindi, associare a ognuna di esse un numero naturale, ossia stabilire una corrispondenza tra l’insieme delle parole A* e l’insieme N dei numeri naturali. Si dice parola vuota la parola a cui è associato 0: essa ha lunghezza nulla e non è costituita da alcun carattere.