Automi e Linguaggi Regolari Alberto Cuesta Cañada Introduzione • Lo scopo della informatica e diventare possibile la communicazione tra l’uomo e i computer. • Prima dobbiamo trovare un linguaggio commune, o meggio, costruirlo. Linguaggi • Definizioni: • Σ= Insieme di letteri • X= a …a |a є Σ = parola (finita) 1 i j • X*=Tutte le parole generate per Σ Linguaggi • Un linguaggio e un insieme di parole (puo essere infinito) da un alfabeto finito. • Si genera con grammatiche con struttura di frase. Phrase Structure Grammars • G={V, Σ, P, S} • Grosso modo una grammatica sono lettere e regole per costrurre parole. • L(G) e’ il linguaggio composto per tutte le parole generate per G. • P=(V- Σ)+ x V* Context Sensitive Grammars • Le produzione hanno la forma: • uAv→uwv dove u,v є V * (forse λ) A є (V- Σ) w є V*, w≠ λ • Lcsf=(anbncn) Context Sensitive Grammars • Grosso modo, un non-terminale determinato puo essere cambiato per una cattena di lettere determinata in un certo contesto. Context Sensitive Grammars • E dimostrabile che queste grammatiche possono essere transformate in altri equivalente: • u→v • A→a u є (V- Σ)+, v є (V- Σ) * A є (V- Σ), a є Σ Context Free Grammars • Le produzione hanno la forma: • A→x dove x є (V) * (forse λ) A є (V- Σ) • Lcfg=(anbn) Context Free Grammars • E dimostrabile che queste grammatiche possono essere transformate in altra equivalente del modo: • A→xv dove x,v є V (forse λ) A є (V- Σ) • Questo serve per produrre alberi binari Context Free Grammars • Definizione: Una parola ‘e in forma canonica se tutte le sue derivazione sono nell stesso senso (destra o sinistra) • S→Sa| λ S S S S a a a Linear Context Free Grammars • Una grammatica di cui tutte le forme possibili sono canoniche a destra (sinistra) se dice che e’ lineale a destra (sinistra). • E’ dimostrabile che queste grammatiche sono equivalenti alle grammatiche regolari. • L=(aibj) Grammars Phrase Structure Grammars Context Sensitive Grammars Context Free Grammars Linear Context Free Grammars Automi • • • • • • Un automa e’ una 5-tupla {Q, Σ, δ, q0, F} Q=Stati. 1 Σ=Alfabeto. b a λ δ =Transizioni. 0 3 b q0 =Stato Iniziale. a 2 F=Stati Finali. a LCF Grammars e Automi • E’ dimostrabile la correspondenza tra Linguaggi Regolari e Automi Finiti. • L=(a+b)* λ 3 λ 0 λ 1 λ 2 λ 5 a 4 b 6 λ λ λ 7 λ 8 λ 9 Operazioni con Automi: AFλ →AFN • Si puo trovare un automa finito non determinista per ogni automa finito con transizioni vuoti: λ 3 λ 0 λ 1 λ 2 λ 5 a 4 b 6 λ λ λ 7 λ 8 λ 9 Operazioni con Automi: AFλ →AFN λ 3 λ 0 λ 1 λ 2 λ 5 a 4 b 6 λ λ λ 7 λ 8 λ • Prendiamo uno stato e troviamo la sua λclousure. • 0 → 0,1,2,3,5,8,9 9 Operazioni con Automi: AFλ →AFN a 4 λ 0 λ b 6 λ • Prendiamo un altro stato diverso e ripetiamo: • 4 → 7,0 7 a 4 Operazioni con Automi: AFλ →AFN b 6 a,b 6 λ • Ripetiamo: • 6 → 6,4 Il metodo finisce quando non c’e’ nessuna transizione vuota Operazioni con Automi: AFN →AFD • Si puo trovare un automa finito determinista per ogni automa finito non determinista: a b 1 3 a b 0 b 2 b a 4 5 a Operazioni con Automi: AFN →AFD Stato a b 0 1 2 1 V 3 2 1,4 V 3 V b 1 a a a,b 4,5 1,4 V,5 V,3 4,5 V,5 V V,5 V V V,3 V V,4,5 V,4,5 V,5 V V V V 3 b a b V 4,5 a,b 0 a b b V,3 2 b a b b 1,4 a a V,4,5 a V,5 Operazioni con Automi: AFD →AFD Minimo • E’ molto utile lavorare con automi minimi: b 1 3 a a a,b b a b 9 5 a,b 0 a b b 7 2 b a b 8 b 4 a a a 6 Operazioni con Automi: AFD →AFD Minimo 5,6,8 є F → B1={1,2,3,4,7,9}, B2={5,6,8} Stato a b B1 0 B1 B1 1 B1 B1 2 B1 B1 3 B1 B2 4 B2 B1 7 B1 B2 9 B2 B1 B2 5 B2 B1 6 B1 B1 8 B2 B1 B1’={0,1,2} B2’={3,7} B3’={4,9} B4’={5,8} B5’={6} Operazioni con Automi: AFD →AFD Minimo Stato a B1 0 B1 b B1 1 B3 B2 2 B3 B3 3 B3 B4 7 B3 B4 4 B5 B3 9 B3 B3 5 B5 B3 8 B5 B3 6 B3 B3 B2 B3 B4 B5 B1’={0} B2’={1} B3’={2} B4’={3,7} B5’={4} B6’={9} B7’={5,8} B8’={6} Operazioni con Automi: AFD →AFD Minimo Blocco Stato a b B1 0 B2 B3 B2 1 B6 B4 B3 2 B5 B6 B4 3 B6 B7 7 B6 B7 B5 4 B8 B4 B6 9 B6 B6 B7 5 B8 B6 8 B8 B6 6 B6 B6 B8 El algoritmo finisce qui, abbiamo tolto due stati dell’ originale. B6 a a B2 b B1 b a B4 b b B3 a B5 a b B7 a B8 a,b a,b Pushdown Automata • Un automa pushdown ha due nastri, uno con il input, e altro che funziona come uno stack. a Automa nell stato Q Z • Questi automi sono correspondenti con le Context Free Grammars. Linear Bounded Automata • Un Linear Bounded Automa ha un solo nastro finito, in cui puo leggere e scrivere a Automa nell stato Q • Questi automi sono correspondenti con le Context Sensitive Grammars. Turing Machines • Una Machina di Turing e’ una Linear Bounded Machine che lavora su un nastro di input infinito. a Automa nell stato Q • Queste machine sono correspondenti con le Phrase Structure Grammars. Conclusione Phrase Structure Grammars Machine di Turing Context Sensitive Grammars Linear Bounded Automi Context Free Grammars Linear Context Free Grammars Pushdown Automi Automi Finiti