# Introduzione ai linguaggi formali
## Introduzione ai linguaggi
### Definizioni base

Diciamo:
* alfabeto: qualsiasi insieme finito di simboli (o caratteri o lettere) e lo indichiamo con $\Sigma ={a_{1},a_{2},...,a_{k}}$ e la sua cardinalità con $|\Sigma |=k$.
* stringa: una sequenza ordinata di elementi dell'alfabeto (anche ripetuti).
* linguaggio formale un insieme di stringhe di lunghezza finita. Le stringhe appartenenti a un linguaggio sono dette frasi (o sentences o phrases in inglese). Il linguaggio è indicato con la lettera $L$
* la cardinalità di un linguaggio formale è il numero delle sue frasi $|L_{x}|=k$, esempio $|{aa,ba,ab}|=3$. Un linguaggio vuoto ha ovviamente lunghezza nulla $|\varnothing |=0$
* numero di occorrenze di un simbolo in una stringa è indicato con il simbolismo $|aaaba|_{a}=4$.
Nel corso di Fondamenti di Informatica, così come nei Laboratori di Programmazione, abbiamo anche osservato che nel nostro computer utilizziamo un alfabeto chiamato ASCII, ad esempio. Esso é fatto degli stessi simboli che compongono le parole di questo testo.
Inoltre possiamo dire che:
* un linguaggio è un insieme di formalismi, con sintattica e semantica definite in modo preciso, tali da consentire una qualche forma di elaborazione.
* esiste un elemento dell'insieme $\epsilon$ (epsilon) chiamato stringa vuota che appartiene all'insieme di tutti i linguaggi.
* due stringhe sono uguali se e solo se hanno la stessa lunghezza e i loro elementi coincidono (in ordine, da sinistra a destra).

### Linguaggi prefix-free

Definiamo prefisso di un linguaggio una stringa non vuota, che è prefisso di tutte le stringhe del linguaggio. Formalmente, definiamo l'insieme dei prefissi di un linguaggio come:
    $Prefixes(L)=\{\ y\ |\ \exists x(x\in L\land x=yz\land y\neq \varepsilon \land z\neq \varepsilon \}$
La notazione precedente fa uso del concetto di concatenazione tra stringhe, formalizzato nella lezione successiva.
Un linguaggio è detto prefix-free se nessun prefisso del linguaggio appartiene al linguaggio stesso: $L\cap Prefixes(L)=\varnothing$
Esempi:
* $L_{1}=\{\ x\ |\ x=a^{n}b^{n}\land n\geq 1\ \}$ è prefix-free $a^{2}b^{2}\in L_{1}\ \$ ma $a^{2}b\notin L_{1},a^{2}\notin L_{1},a\notin L_{1}$
* $L_{2}=\{\ x\ |\ x=a^{m}b^{n}\land m,n\geq 1\ \}$ non è prefix-free $a^{2}b^{2}\in L_{1}\ \$ e $a^{2}b\in L_{1}$

## Automi

Ora che sappiamo che cosa é un Linguaggio, abbiamo scoperto che é accettato da un Automa. (Quello che eravamo noi qualche riga fa..) Cosa sia un Automa, però é necessario non sia una definizione ambigua.
Un automa è un meccanismo in grado di eseguire un confronto su un input dato e modificare il suo stato interno fino a produrre un eventuale output.
Definiamo eventuale perché ricordiamoci che tacere equivale ad accettare un linguaggio qualsiasi ma non interagire, produrre un output di accettazione, in ogni caso. (Chi tace acconsente)
Come ultimo esempio su noi stessi,
ecco come viene modificato uno dei vostri stati interni riconoscendo la stringa:
Si scherza, ovviamente..
Questo per indurre lo studente ad osservare che gli automi di cui si vuole parlare sono macchine che possiedono degli stati interni che, in base ad un input esterno, possono essere percorsi fino ad indurre l'Automa in un particolare stato.
Per poter chiarire meglio, evitando di fare esempi che possano involontariamente offendere il lettore :) , utilizzeremo l'esempio reale della macchina del caffè.

### Definizione di Automa

Un automa A é un oggetto composto da una quintupla così descritta:
* Un insieme di stati Q
* Un Alfabeto di Input Σ
* Una funzione di transizione σ
* Lo stato Iniziale q0
* Un insieme di stati finali

### La Macchina del Caffè

Siamo circondati di diversi automi che incontriamo nella vita quotidiana e che non ci soffermiamo mai ad osservare. Tra i tanti, potremo citare lo sportello di una banca, o il distributore di sigarette, o quello di medicinali. Pensando all'Automa "MacchinaDelCaffè" possiamo immaginare che essa abbia:
* Un insieme di stati
* Un Alfabeto in Input
* Una funzione di transizione
* Uno stato iniziale
* Un insieme di stati accettanti
Tra i vari strumenti di cui possiamo godere nella Rete, esiste JFlap che ci consente di poter illustrare in un modo più diretto questo tipo di oggetti che sono gli Automi.