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:

---

"sbronzo!"

---

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
L'Automa deve potersi trovare in stati definiti dalle varie combinazioni di input.
• Un Alfabeto di Input Σ
Il cambiamento degli stati interni avviene su una serie di simboli di Input.
• Una funzione di transizione σ
La funzione di transizione definisce come cambi lo stato interno dell'Automa in funzione dello stato in cui esso si trovi al momento del nuovo input. Essa è una funzione QxΣ→Q, prende dunque in input uno stato ed un simbolo di input e dà in output il nuovo stato dell'automa.
• Lo stato Iniziale q0
Rappresenta lo stato assunto dall'automa alla sola lettura della stringa vuota ε.
• Un insieme di stati finali
Nell'insieme degli stati interni é possibile definirne alcuni che sono particolari. Questi sono gli stati accettanti; ovvero quegli stati raggiunti dall'automa solo nel caso in cui venga letta una stringa appartenente al linguaggio riconosciuto dall'automa.

---

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
Ad esempio gli stati che sono necessari per riconoscere un valore introdotto di 35 cents (costo del caffè?)
• Un Alfabeto in Input
L'Automa deve riconoscere le monete da 5, 10 o 20 centesimi. Qualora, didatticamente, non considerassimo la possibilità di accettare monete da 50€/cents, potremmo benissimo definire l'Alfabeto con i simboli { 5, 10, 20 }
• Una funzione di transizione
L'inserimento delle monete provoca la modifica dello stato interno all'automa. Banalmente essa é in grado si sapere quanto credito é stato inserito.
• Uno stato iniziale
La macchina é accesa e pronta. Il credito é pari a 0 (zero)
• Un insieme di stati accettanti
Tutti gli stati interni per cui é possibile produrre un output. (Ovvero: Credito >= Costo Caffè)

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.

JFlap disegna la nostra Macchina del Caffè