La concatenzione tra due stringhe, detto anche prodotto tra due stringhe, è definito come:
- siano e due stringhe, allora la loro concatenzione è .
La concatenzione è anche indicata con . Gode della proprietà associativa e dell'additività della lunghezza .
Ha come elemento neutro la stringa vuota: .
Diciamo che è sottostringa di se e solo se:
- per qualche stringa (detta prefisso) e (detta suffisso).
è sottostringa propria se e solo se e .
L'operazione di riflessione è definita come:
- sia allora la sua riflessione è .
Gode delle seguenti proprietà:
- riflessiva:
- distributiva:
- valore nullo:
Si definisce ripetizione o potenza di una stringa la concatenazione di se stessa volte:
- con . Se , allora
Esempi:
N.B.: ripetizione e riflessione hanno la precedenza sulla concatenzione! Esempio: e .
Alcune operazioni sui linguaggi sono l'estensione di quelle sulle stringhe.
La riflessione di un linguaggio è l'insieme di tutte le stringhe riflesse del linguaggio:
- sia un linguaggio, allora
La concatenazione di un linguaggio è definita come il linguaggio contenente la concatenazione delle stringhe dei linguaggi concatenati:
N.B.
La ripetizione o potenza di un linguaggio viene definita ricorsivamente:
- per
N.B.
Esempio:
Come visto la potenza produce un set di stringhe di dimensione fissa e finita . Utilizzando la stringa vuota è possibile ottenere il set di stringhe con lunghezza minore di m.
Esempio:
I linguaggi godono delle classiche operazioni insiemistiche:
- : unione (insieme composto da tutte le stringhe che compongono il primo linguaggio o il secondo linguaggio.)
- : intersezione (insieme composto da tutte le stringhe che compongono il primo linguaggio e il secondo linguaggio.)
- : differenza (insieme composto da tutte le stringhe che compongono il primo linguaggio ma non il secondo linguaggio.)
- : inclusione
- : inclusione stretta
- : uguaglianza
Definiamo linguaggio universale di un alfabeto come l'insieme di tutte le stringhe di qualsiasi lunghezza sull'alfabeto:
Definiamo complemento di un linguaggio su un alfabeto :
N.B.:
- .
- Il complemento di un linguaggio finito è sempre infinito;
- Il complemento di un linguaggio infinito non è sempre finito.
La chiusura di Kleene o operatore stella è la chisura riflessiva e transitiva dell'operazione di concatenazione.
Informalmente, questo insieme di stringhe è quello che è possibile generare concatenando due stringhe di L, anche con ripetizioni.
Ad esempio:
è evidentemente sempre infinito, qualsiasi sia il linguaggio . Può capitare che , ad esempio: .
N.B.:
Spesso si utilizza la sintassi per dire che il linguaggio è un linguaggio sull'alfabeto .
La chiusura di Kleene gode delle seguenti proprietà:
- monotonicità:
- chiusura alla concatenazione:
- idempotenza:
- commutatività con riflessione:
L'operatore cross è la chisura transitiva ma non riflessiva dell'operazione di concatenazione. Sostanzialmente rispetto al precedente l'unione non include la prima potenza
L'operatore quoziente, identificato dalla slash (non backslash!). Definito come:
.
Esempio: