Linguaggi formali e automi

Ciao!

Sono Federico Tabellini, l’autore di questi appunti.

Siccome mi rendo conto che a volte la mia scrittura può non essere chiara e immediata ti lascio la mia mail dopo puoi contattarmi per chiedermi di trascriverti una frase/parola che non riesci a leggere. Indica nell’oggetto il nome della materia oppure mandami uno screen specificando la parola.

Non appena potrò risponderò alla tua mail.

fede.tabellini@gmail.com

NB:

• Non spiego concetti, traduco e basta.
• Un buon quaderno di appunti deve comunque essere accompagnato da studio e pazienza.
• Accetto consigli/critiche (solo se costruttive)

Spero che questi appunti ti aiutino

Buono Studio

Linguaggi Formali e Automi

Introduzione

Linguaggi Formali e Automi → Cominciamo Analizzando il Titolo

• Insiemi di Regole che Permettono la Comunicazione
• Esempi:
  • Linguaggi Naturali → Comunicazione tra individui (es. Italiano, Inglese, Tedesco ecc...)
  • Linguaggi di Programmazione → Comunicazione Uomo-Macchina (es. Java, C++, Python)
  • Segnaletica Stradale
  • Codici e Morse

Come insegnare un linguaggio?

• Prima spieghiamo il Lessico: (fornire conoscenza delle parole più comuni)
  • Formiamo un Vocabolario
• Spiegazione Sintassi (come formare frasi corrette)
  • Formiamo Regole Grammaticali

Formali: Aspetti che permettono di dare specifiche e precise a un Linguaggio

• Utilizziamo strumenti matematici e/o di Informatica Teorica

Pro: Potere trattare i linguaggi in maniera automatica (senza intervento diretto dell’uomo)

• Esempio:
  • Compilatori → Verificano sintassi e lessico di un programmazione
  • E ottimizzano la traduzione in linguaggio Macchina (.exe)

Linguaggi Naturali: Sono più Complessi e si dividono in:

• Parlato vs Voce sintetica: Toni
• Scritto
  • Messaggio: Sequenze di Caratteri (compresi spazi e punteggiatura)
• Vengono usate Macchine e ne vengono esemplificati Campi

Sperimentare un sottoinsieme del Linguaggio:

• (Numero di messaggi, Parallellismo)
• per comunicarli trattabili in maniera automatica

- Esempio: Traduttori Automatici

• (Insoddisfacenti per la maggior parte dei casi)

ESEMPIO 1

Unioni Intersezioni Complemento

L₂={a², b}^*

• L₁L₂=∑\{b}^* (Insieme di tutte le parole che contengono SOLO a, solo b)
• L₃={b}^*
• L₄=∑\L₂
• Es: parola a²b ∈ L₁L₂, parola b ∉ L₁L₂
• L_i∩L_j = ∅
• L_i∪L_j=∑\{b}^* per tutta i possibili coppie (e il suo complementare nostro)

ESEMPIO 2

Prodotto

• L₂={0,1}
• L₁L₂ = insieme di tutte le parole che iniziano con 1
• -100001 ∈ L₁L₂, ma 000001 ∉ L₁L₂
• L₂L₁ = insieme di tutte le parole che terminano con 1
• 4000 ∈ L₂L₁ ma 10000 ∉ L₂L₁

Possiamo concludere quindi che L₁L₂ ≠ L₂L₁ (Commutativo NO)

Può però valere la prop. Commutativa SOLO nel caso di prodotti tra linguaggi sulla stessa

ESEMPIO 3

Chiusura di Kleen

• In questo caso L⁺=L^*\{ε} poiché devo prenderlo almeno una volta MA se ε ∈ L (L=∑)

ESEMPI VARI

• L₁=Fisico, Astrol
• L=∑\{Nom}

Posso allora scrivere D come:

D = { x | F_A(x⟨s⟩x) } ↕

Ma cosa succede se x non codifica alcun Programma?

Se l’interprete non codifica alcun programma per x allora termina con un errore.

Dobbiamo esibire una procedura che termini per x∈D e non termini altrimenti.

Procedura RIE.LUNN (x∈{0,1}^*)

• (i) F_A(x⟨s⟩x)
• (ii) altrimenti 1

Dimostriamo per assurdo che D non è Ricorsivo.

Procedura ASSURDO (x∈{0,1}^*)

if x∈D returns (¬ F_A(x⟨s⟩x))

else returns 0

• Cos’è x∈D? Una funzione c che termina sempre

Assurdo(e) = F_A(e⟨s⟩e) = F_A(e⟨s⟩e)?

Conclusione: D deve essere per forza Non Ricorsivo

Dobbiamo fare qualche modifica alla procedura.

I Modifica: Passo x come input alla procedura

II Modifica: Sostituisco 3) con: if (x ∈ T) {return (1);}

Grazie a queste modifiche ho generato la mia procedura V

che ritorna 1 se trova la parola e non termina altrimenti.

ESEMPIO: L=Espressioni Aritmetiche di Somme e Prodotti

1) 0, x ∈ L

2) x, y ∈ L xxy - x.y ∈ L

3) Tutto ciò che non è permesso tramite 1) ed 2) ∉ L

G per L: G(Σ= {0, 9, x, ;},

• M = {E
• P = {E → C; (E + E); (E x E) ; C → O ; ......;}
• S = { }

[NB Non sostituire + e x con Op]

Ossia: E → C

E → E op E

Op → +, x

Parola in L: ((0+9) x 5)

E ⇒ (E x E) ⇒ (E x E)

((E+E) x E) ⇒ ((G+E) x E) ⇒ ((C+C x E)

((C+C) x E) ((C+C) x C x C) ⇒ (0+C) x C) ⇒ ((0+9) x C) ⇒ ((0+9) x 5) Parola finale

CLASSIFICAZIONE di CHOMSKY (Provvisoria):

Classificazione di parte della grammatica più complessa alla più semplice.

In base alla produzione della giurisdizione: α → β α ∈ (Σ∪M)* β ∈ (Σ∪M)*

Tipo 0: Nessuna Restrizione. Tutte le grammatiche rientrano in questa canonica di produzione.

1. α → β | α ≠ L | P(gα ) = Lunghezza p ≥ lunghezza α (Può ogni produzione)
2. Tipo 2: Almeno B se A è elemento di B (B ∈ (Σ∪M)+ )
3. Tipo 3: A → a B se X ∈ M ed a ∈ X {a, b}

Ogni simbolo dell'alfabeto è di tipo 1

Ogni simbolo delle acarattere è ASCII {E}

Ogni simbolo terminal forma la parola vuota

Ogni grammatica di tipo n è anche di tipo z m (anche dei tipi precedenti ed n = m)

Perché ogni tipo rispetta le condizioni dei tipi precedenti.

Teoria degli Automì

Supponiamo di dover modellare due pagine web, un link(l) che porta da P₁ a P₂ e due pulsanti: Reload per ricaricare la pagina e Back per tornare alla precedente.

Avremmo uno: Portando da P_i se si verifica il click reload su P_j. Se si verifica ritorno sulla pagina e con back ritorno alle penultime pagine caricate.

Lo stato varia quindi a seconda dell'evento verificatosi.

Automa

Prima approssimazione: Sistema S a cui do in input un messaggio su Σ, messaggio = Σ_i, e in base al messaggio acquisito dà in output (0 oppure 1)

Per capire cosa fa la "scatola" dobbiamo fare degli esperimenti:

Esperimento

1. Posso posto cu come input
2. Al termine, troverò il sistema e capo e indurerà

0→Messaggio w non è

1→Messaggio w

Accettato da S

Automa = Riconoscitore di Linguaggi

Principali Caratteristiche degli Automi

1. Comportamento interno dipende dal messaggio di input e dallo stato in cui si trova il sistema. Quando inizio la lettura.
2. Ad ogni istante di tempo S si trova in questo stato qe Q.
3. Alla lettura di un simbolo, S può cambiare stato.
   • Se S_n è in qe e legge w_e allora indica con δ (qe, w) lo stato raggiunto da S partendo da qe dopo lettura di w.

Funzione di Transizione

Output dipende dello stato in cui il sistema soggiorna dopo aver letto w

Se raggiungo lo stato e l'uscita si indica con λ(q)→C=0

Funzione di Uscita

Quindi formalmente, un Automa A è:

A=<Σ, Q, δ, q₀, F>

Stato iniziale

Stati finali