Linguaggio formale

Note

Un linguaggio è uno strumento per esprimere modelli. Ogni linguaggio è definito su un alfabeto, che è un insieme finito di simboli.

Esempi di linguaggio

Lingue naturali: Italiano, Francese, Inglese, Giapponese Linguaggi sintetici: C, Java, XML, JSON Linguaggi grafici: cartelli stradali, simboli di lavaggio negli indumenti Linguaggi acustici: musica, fischi degli arbitri sportivi

Esempi di alfabeto

Alfabeto latino: $\{a,b,c,\cdots ,z\}$ Binario: $\{0,1\}$

Un linguaggio può essere usato per definire l’insieme di soluzioni di un problema, e per esprimere un problema stesso.

Stringhe

Note

Definiamo una stringa come una sequenza ordinata e finita di elementi di un alfabeto $A$. Riguardante ad una stringa definiamo:

• Lunghezza di una stringa, cioè il numero di elementi come: $|a|$
• Stringa di lunghezza nulla $\epsilon$, con $|\epsilon |=0$
• Insieme di tutte le stringhe (inclusivo di $\epsilon$) su $A$: $A^{\ast }$
• Operatore di concatenazione $.$ (omissibile)

Siccome l’operatore di concatenazione $.$ è binario, associativo e non commutativo, si può costruire il monoide libero dell’alfabeto $A$, $(A^{\ast },.)$ con elemento neutro $\epsilon$.

Linguaggio su un alfabeto $A$

Note

Un linguaggio $L$ su un alfabeto $A$ è un sottoinsieme di $A^{\ast }$, e quindi un insieme di parole di $A$.

Esempio

L’italiano è un linguaggio su $A=\{a,b,c,\cdots ,z,\_\}$. I file PDF sono un linguaggio su $A=\{0,1\}$. I numeri in base $4$ sono un linguaggio su $A=\{0,1,2,3\}$. Il DNA è un linguaggio codificabile su $A=\{C,G,A,T\}$.

Notiamo che se $|A|<\infty$, non necessariamente $L<\infty$.

Siccome i linguaggi sono insiemi valgono le operazioni insiemistiche come $\cup ,\cap ,\setminus ,\neg$. In particolare il complemento $\neg L=\bar{L}$ è definito rispetto ad $A^{\ast }$, cioè: $\neg L=A^{\ast }\setminus L$.

Concatenazioni tra linguaggi

Note

Dati un linguaggio $L_1$ su $A_1$, e un linguaggio $L_2$ su $A_2$, si ha che $L_1.L_2$ definito su $A_1\cup A_2$ è:

$$L_1.L_2=\{x.y\mid x\in L_1,y\in L_2\}$$

Si ha inoltre che dato un linguaggio $L$ e $n\in \mathbb{N}$, $L^n$ è definita come la concatenazione di se stesso $n$ volte:

$$\{\begin{array}{l}{L}^0=\{\epsilon \}\\ L^n=L^{n-1}.L\end{array}$$

Definiamo inoltre l’operatore $+$ di un alfabeto, che indica stringhe fatte concatenando uno o più elementi dell’insieme. Per estensione ai linguaggi definiamo:

$$L^{\ast }=\bigcup _{n=0}^{\infty }{L}^n{L}^{+}=\bigcup _{n=1}^{\infty }{L}^n$$

Nella pratica, l’intersezione tra linguaggi indica la compatibilità tra di loro, mentre la concatenazione di linguaggi consente di descrivere più agevolmente formati complessi.

Esempio di concatenazione

$$\begin{array}{rl}& L_1=\{0,1{\}}^{\ast }{L}_2=\{a,b{\}}^{\ast }\\ & L_1.L_2=\{\epsilon ,0,1,0a,011b,0aba,\cdots \}\end{array}$$

In questo esempio $a_1\notin L_1.L_2$ perché la concatenazione non è commutativa.

Esempio di concatenazione

Sia un alfabeto $A=\{0,1\}$, allora $A^{+}=\{0,1,00,01,10,\cdots \}$. Per quanto riguarda ai linguaggi:

• Formato di pacchetto di dati su una rete $L_{\text{header}}.L_{\text{dati}}.L_{\text{trailer}}$
• Archivio di dati tar o zip: $L_{\text{indice}}.L_{\text{file}}^n$

Traduzioni

Note

Una traduzione è una mappa $\tau (\cdot ):L_1\to L_2$, cioè mette in corrispondenza parole di due linguaggi.

Famiglia di linguaggi

Note

Una famiglia di linguaggi è un insieme $\mathbb{L}$ i cui elementi sono linguaggi. È chiusa rispetto ad un’operazione $\star$ se $\forall L_1,L_2\in L{L}_1\star L_2\in L$.