La concatenazione dei linguaggi

La concatenazione di due linguaggi, che chiameremo $ A $ e $ B $, è il linguaggio risultante che contiene tutte le possibili stringhe che possono essere formate prendendo una stringa da $ A $ e concatenandola con una stringa da $ B $.

Matematicamente, la concatenazione di $ A $ e $ B $, che indichiamo con $ AB $, è definita come:

$$ AB = \{ ab \mid a \in A \text{ e } b \in B \} $$

Dove $ a $ è una stringa in $ A $ e $ b $ è una stringa in $ B $. Ogni elemento di $ AB $ è la concatenazione di una stringa da $ A $ seguita da una stringa da $ B $.

Ricordandosi che $ A^0 = λ $ è l'elemento neutro ossia una stringa vuota "" mentre $ A^n=A_1 \cdot ... \cdot A_n $ equivale a concatenare una stringa con se stessa per n volte.

Esempio

Consideriamo due semplici linguaggi A e B composti ciascuno da due parole:

$$ A = \{ "gatto", "cane" \} $$

$$ B = \{ "nero", "bianco" \} $$

Allora la concatenazione dei linguaggi $ A $ e $ B $ sarebbe:

$$ AB = \{ "gattonero", "gattobianco", "canenero", "canebianco" \} $$

In altre parole la concatenazione AB è l'insieme di tutte le stringhe che si possono formare prendendo una stringa da A e unendola a una da B.

Quindi, ogni stringa in $ AB $ è il risultato di aver preso una stringa da $ A $ e averla unita con una stringa da $ B $.