Alfabeto del linguaggio
Nella teoria dell'informazione, un "alfabeto" è un insieme di simboli o caratteri distinti dai quali si costruiscono le stringhe o i messaggi.
Ogni simbolo dell'alfabeto è univoco e distinto da ogni altro simbolo ed è un elemento di base per la creazione di messaggi in un sistema di comunicazione o elaborazione dati.
Di solito, un alfabeto è un insieme finito.
Ad esempio, l'alfabeto inglese ha 26 simboli (lettere), l'alfabeto binario ha 2 simboli (0 e 1), ecc.
$$ Σ_{inglese} = \{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z \} $$
$$ Σ_{binario} = \{0,1\} $$
Combinando i simboli dell'alfabeto in sequenze, si creano stringhe che possono rappresentare dati, informazioni, istruzioni, ecc.
Ad esempio, la parola "cane" è una stringa composta da una sequenza di quattro lettere dell'alfabeto inglese
$$ s_1 = "cane" $$
La parola "gatto" è un'altra stringa ottenuta concatenando le lettere dell'alfabeto inglese.
$$ s_2 = "gatto" $$
Le stringhe formate dall'alfabeto possono essere trasmesse attraverso un canale di comunicazione o memorizzate per un utilizzo futuro.
I simboli dell'alfabeto possono essere usati per codificare informazioni. In informatica, l'alfabeto binario (0 e 1) è usato per codificare quasi tutti i tipi di dati, in modo da poterli elaborare e trasmettere tramite dei dispositivi elettronici (es. computer, satelliti, interfacce telematiche, ecc.).
Esempio
Immaginiamo di avere un sistema di comunicazione semplice dove vogliamo trasmettere solamente se fa caldo o freddo.
Per questo sistema, potremmo definire un alfabeto molto semplice di soli due simboli:
$$ \Sigma = \{C, F\} $$
Dove:
- "C" sta per "Caldo"
- "F" sta per "Freddo"
Questo è l'alfabeto del nostro sistema di comunicazione. Ogni messaggio che vogliamo inviare deve essere composto utilizzando solo questi due simboli.
Per esempio, una sequenza come "CCFFC" potrebbe indicare una serie di giorni in cui prima fa caldo, poi freddo, poi di nuovo caldo.
Se volessimo espandere il nostro sistema per comunicare non solo la temperatura, ma anche se è soleggiato o nuvoloso, potremmo aggiungere altri due simboli al nostro alfabeto:
$$ \Sigma = \{C, F, S, N\} $$
Dove ora abbiamo:
- "S" per "Soleggiato"
- "N" per "Nuvoloso"
Con questo nuovo alfabeto a quattro simboli, potremmo codificare messaggi più dettagliati come "CSNF" che potrebbe significare "Un giorno caldo e soleggiato seguito da un giorno freddo e nuvoloso".
Questo esempio dimostra il concetto di base di un alfabeto nella teoria dell'informazione e come l'uso di un alfabeto può essere applicato per codificare informazioni in un modo che può essere facilmente compreso e trasmesso all'interno di un dato sistema.
Le proprietà di un alfabeto
Nel contesto della teoria dell'informazione, spesso si studiano le proprietà degli alfabeti per capire come possono essere usati in modo efficiente per codificare, trasmettere e comprimere informazioni.
La regola fondamentale di un alfabeto
Per qualificare un insieme finito Σ come alfabeto, è necessario che soddisfi una regola fondamentale:
Due sequenze finite di simboli tratti da un alfabeto Σ si considerano uguali esclusivamente quando i corrispondenti simboli di entrambe le sequenze sono identici e compaiono nello stesso ordine.
Esempio. Prendiamo in considerazione due insiemi: \( \Sigma = \{0, 1\} \) e \( \Sigma' = \{00, 01\} \). Entrambi questi insiemi sono alfabeti validi secondo la teoria dell'informazione. Questo perché permettono di formare sequenze di simboli (stringhe) in cui l'ordine e l'identità di ogni simbolo possono essere chiaramente determinati senza ambiguità. Per esempio, nella stringa "010" formata dall'alfabeto \( \Sigma \), è evidente che la sequenza è composta da "0", "1", "0". Analogamente, una stringa come "0001" dell'alfabeto \( \Sigma' \) è chiaramente una concatenazione di "00", "01". D'altra parte, un insieme come \( \Sigma'' = \{1, 11\} \) non può essere considerato un alfabeto valido perché la sequenza "111" potrebbe essere interpretata in modi diversi: potrebbe essere vista come "1", "11", oppure "11", "1", o anche tre "1" consecutivi. Questa ambiguità nella decodifica delle stringhe contraddice la definizione di un alfabeto nella teoria dell'informazione, dove ogni sequenza dovrebbe avere una sola interpretazione chiara.
Pertanto, un alfabeto non può contenere la stringa vuota 𝜆 perché 𝜆x = x𝜆 sono sequenze diverse uguali. E questo non è possibile in un alfabeto.
Un altro teorema importante è il teorema di McMillan che fornisce un limite su quanto densamente possiamo "impacchettare" informazioni senza perdere l'abilità di distinguere una stringa dall'altra.
Il teorema di McMillan ci permette di capire se un insieme di stringhe {s1,s2,...,sn} costruito su un alfabeto di n simboli è a sua volta un alfabeto oppure no.
