Linguaggi formali
Cos'è un linguaggio formale
Un linguaggio formale è un insieme composto da un alfabeto e parole.
L'alfabeto
Un alfabeto E è un insieme finito e non vuoto di simboli.
La cardinalità dell'insieme |E| indica il numero dei simboli dell'alfabeto.
Esempio
Il linguaggio binario ha un alfabeto composto da due soli simboli, lo zero e l'uno.
$$ E = \{ 0,1 \} $$
La cardinalità dell'insieme è 2.
$$ |E| = 2 $$
Le parole
Le parole (o stringhe) sono sequenze di simboli appartenenti all'alfabeto.
Esempio
Dato un alfabeto composto da tre simboli
$$ E = \{ A,B,C \} $$
Sono esempi di parole le seguenti:
$$ w_1 = ABC \\ w_2 = ABBA \\ w_3 = BACCA \\ \vdots $$
Ogni parola (word) ha una lunghezza |w| pari al numero dei simboli anche ripetuti che la compongono.
$$ |w_1|=3 \\ |w_2|=4 \\ |w_3|=5 \\ $$
Nota. Per misurare la frequenza di un singolo simbolo x nella parola (occorrenze) si scrive |w|_x. Ad esempio $$ |w_3|_C=2 $$
L'insieme di tutte le parole possibili con un alfabeto E si indica con il simbolo E*.
Non occorre che le parole abbiano un significato.
Pertanto, l'insieme E* è un insieme infinito perché è composto da sequenze di simboli senza un limite di lunghezza.
La stringa vuota
Nell'insieme E* è definita anche la stringa vuota ossia una parola di lunghezza pari a zero.
La stringa vuota è indicata con il simbolo epsilon ε.
Il prefisso, la sottostringa e il suffisso
Una parola può essere composta da tre componenti:
- Prefisso. E' la sequenza di caratteri iniziale (u).
- Sottostringa. E' la sequenza di caratteri intermedia (v) tra il prefisso e il suffisso.
- Suffisso. E' la sequenza di caratteri terminale (z) della parola.
Esempio. La parola w1=BACCA è composta dai seguenti prefissi possibili B, BA, BAC, BACC, BACCA. I suffissi possibili sono, invece, A, CA, CCA, ACCA, BACCA. La scelta del prefisso e del suffisso determina indirettamente l'insieme delle sottostringhe. Ad esempio, se il prefisso è BA e il suffisso è CA, allora una sottostringa è C.
Le operazioni sulle parole
Le principali operazioni sulle parole sono le seguenti:
- La concatenazione
Due parole sono unite per formare una singola parola. - La proiezione
Da una parola si eliminano dei simboli.
Linguaggio
Un linguaggio L è un insieme di parole definite su un alfabeto E.
Il numero delle parole del linguaggio indica la cardinalità del linguaggio stesso.
$$ |L| $$
Pertanto, un linguaggio è un insieme finito.
Nota. In alcuni casi può comunque essere anche un insieme infinito oppure un insieme vuoto se è composto soltanto dalla parola vuota (stringa nulla e)
Esempio
Dato un alfabeto con tre lettere
$$ E=\{ A,B,C \} $$
e un insieme infinito E' di sequenze possibili (parole)
$$ A, AB, BA, ABC, BAC, ... $$
Il linguaggio L1 è un sottoinsieme finito di parole
$$ L_1 = \{ AB, BA \} $$
Il linguaggio L2 è, invece, un sottoinsieme infinito di parole.
$$ L_1 = \{ w \in E' : |w|>5 \} $$
Comprende tutte le parole composte più di 5 simboli.
Le operazioni sul linguaggio
I principali operatori sui linguaggi sono:
- Unione
Due linguaggi sono uniti per formare un unico linguaggi. - Intersezione
E' il sottoinsieme delle parole in comune di due linguaggi. - Concatenazione
E' un insieme con la concatenazione delle parole di due linguaggi. - Stella di Kleen
E' la concatenazione delle parole di un linguaggio per n volte. - Il complemento
E' l'insieme delle parole non presenti nel linguaggio L rispetto a un altro linguaggio o insieme di parole. - Composizione concorrente
E' l'insieme delle parole che sono proiezioni appartenenti a due linguaggi.
Tipi di linguaggi formali
Esistono diverse categorie di linguaggi formali
- Linguaggi ricorsivamente enumerabili
E' la classe dei linguaggi accettati dalle macchine di Turing. Questa colasse include i linguaggi regolari, i linguaggi liberi dal contesto e i linguaggi di Petri.Nota. I linguaggi ricorsivamente enumerabili sono la classe più alta nella gerarchia dei linguaggi perché include tutti gli altri. Pertanto, la macchina di Turing è in grado di accettare tutte le altre tipologie di linguaggi ed è in grado di rappresentare tutti i sistemi. Gli altri linguaggi hanno una potenza descrittiva più limitata. Tuttavia, la macchina di Turing ha lo svantaggio della complessità.
- Linguaggi dipendenti dal contesto
E' la classe dei linguaggi accettati dagli automi limitati inferiormente. E' un sottoinsieme dei linguaggi ricorsivamente enumerabili. Include i liguaggi di Petri e i linguaggi liberi dal contesto. - Linguaggi liberi dal contesto
E' la classe dei linguaggi accettati dagli automi a pila - Linguaggi di Petri
E' la classe dei linguaggi accettati dalle reti di Petri.Nota. Le reti di Petri sono una buona via di mezzo perché garantiscono un potere descrittivo accettabile, superiore a quello degli automi, e un discreto livello di semplicità di utilizzo.
- Linguaggi regolari
E' la classe dei linguaggi accettati dagli automi finiti. E' un sottoinsieme dei linguaggi dipendenti dal contesto. Identifica l'intersezione tra i linguaggi liberi dal contesto e i linguaggi di Petri.Nota. Gli automi a stati finiti sono il modello più semplic ma hanno un potere descrittivo limitato ai soli linguaggi regolari. Tuttavia, la semplicità è un loro punto di forza. Quindi, laddove è possibile usarli, sono preferibili agli altri.
E così via.
