Linguaggio

Introduzione

La teoria dei linguaggi formali nasce con l'obiettivo di studiare in modo sistematico le regolarità che si manifestano nei linguaggi naturali.

Con il passare del tempo la disciplina si è sviluppata fino a comprendere diversi strumenti concettuali di grande interesse per l'informatica teorica, molti dei quali verranno presentati in questo corso.

Per comprenderli appieno è necessario comprendere che cosa si intenda, in questo contesto, con la parola linguaggio; lo scopo del presente modulo è proprio la presentazione di tale concetto, unitamente alla definizione delle principali idee ad esso collegate.

L'alfabeto

Alla base di ogni linguaggio formale c'è un alfabeto, inteso semplicemente come un insieme finito di simboli. Anche se la parola richiama subito alla memoria le lettere con cui componiamo le parole, in questo contesto il termine va interpretato in un senso più generale, ossia come un insieme finito di simboli di qualunque genere, siano essi lettere, cifre o qualunque tipologia di segno.

Nella teoria dei linguaggi formali l'alfabeto ha un ruolo centrale, in quanto ogni parola presente nel linguaggio è derivata da esso. Proprio per questo motivo quando si studia o si progetta un linguaggio è fondamentale prestare grande attenzione all'alfabeto, poiché la sua comprensione è il primo passo verso la costruzione di messaggi sensati.

Stabilita l'esistenza di un alfabeto, il suo impiego principale consiste nella produzione delle parole, oggetto di studio della prossima sezione.

La parola

Dato un alfabeto $A$, una parola è una successione finita di simboli presi dall'alfabeto. Indicando con $s_1,s_2,...,s_n$ tali simboli, la parola $w$ si scriverà semplicemente giustapponendo i simboli stessi: $w=s_1{s}_2...s_n$.

Data una parola $w$, con la notazione $|w|$ si intende la lunghezza della parola, da interpretare come il numero di simboli di cui è composta. Ad esempio, la parola $w=ciao$ formata utilizzando le lettere dell'alfabeto latino è composta da quattro simboli, quindi $|w|=4$.

In qualche caso può essere utile considerare la parola vuota o stringa vuota, indicata convenzionalmente con la lettera $ϵ$ oppure con $\lambda$. In questo caso, $|ϵ|=|\lambda |=0$.

Le potenze di un alfabeto

Un alfabeto $A$ può essere interpretato in due modi diversi: o come insieme di simboli con cui costruire le parole, oppure come insieme di parole composte da un simbolo solo. Considerando che le due interpretazioni hanno significati profondamente diversi è stato deciso di distinguerle indicando con $A^1$ l'insieme che contiene parole.

Intuitivamente si potrà supporre l'esistenza di un insieme $A^2$ che contiene tutte le parole generate dall'alfabeto $A$ e composte da due simboli; più in generale, $A^n$ indicherà l'insieme di tutte le parole generate dall'alfabeto $A$ e composte da n simboli.

Gli insiemi $A^1,A^2,...,A^n,...$ prendono il nome di potenze dell'alfabeto $A$.

Particolare attenzione merita la potenza $A^0$, contenente tutte le stringhe generate dall'alfabeto e dotate di lunghezza nulla: evidentemente questa potenza contiene solamente la stringa nulla. Potremo quindi scrivere $A^0=\left\{ϵ\right\}$.

Gli operatori di Kleene

L'insieme alfabeto contiene tutto il potenziale necessario per creare un linguaggio, in quanto da esso possono essere create tutte le possibili parole. Un modo per generarle potrebbe consistere nella creazione di un insieme all'interno del quale mettere prima tutte le parole di lunghezza 1, poi tutte le parole di lunghezza 2, e così via; questo obiettivo è raggiungibile impiegando l'unione insiemistica e sfruttando le potenze dell'alfabeto.

Formalmente diremo che, dato un alfabeto $A$, l'insieme di tutte le parole generabili dall'alfabeto si indica con la notazione $A^{*}$ ed è tale che:

$A^{*}=\bigcup _{n\in \mathbb{N}}{A}^n$

L'operatore star

L'operatore indicato con ${*}^{}$ è chiamato star di Kleene ed è impiegato per generare un monoide libero sull'insieme cui viene applicato.

La concatenazione di parole

La concatenazione di due stringhe $v$ e $w$ è la stringa $z$ ottenuta giustapponendo tutti i simboli della stringa $w$ a quelli della stringa $v$. Più precisamente, indicando con $w=w_1{w}_2{w}_3...w_m$ la stringa $w$ e con $v=v_1{v}_2{v}_3...v_n$ la stringa $v$, la stringa $z=z_1{z}_2{z}_3...z_{n-1}{z}_n{z}_{n+1}...z_{n+m}$, concatenazione delle parole v e w, si scriverà: $v\cdot w=z$, inoltre il generico simbolo $z_i$ assumerà il valore $z_i=v_i$ quando $i\le n$ e $z_i=w_{i-n}$ quando $n<i\le m$. Si può inoltre concludere che $|v|=n$, $|w|=m$ e $|z|=n+m$.