LFA - Linguaggi Formali Autonomi

Eliminazione delle regole del tipo A B

A○ → σBA○ → σA○ → εA B.○ →Questa grammatica tuttavia non è di tipo 3 solo per la presenza di regole del tipo A B. Allo→scopo di eliminare regole di questo tipo, si considerino tutte le derivazioni del tipo F * H, dove⇒​ G​F e H sono metasimboli e si proceda:per ogni regola A si considerano tutte le coppie di metasimboli F ed H per cui F *○ → σB, ⇒​ G​A e B * H e si aggiungono le regole F infatti risulta possibile nella grammatica la⇒​ → σH;G​derivazione F * A * H,​ che equivale a riscrivere F come⇒​ ⇒​ σB ⇒​ σH.G​ G ​ G​ ​per ogni regola A oppure A si aggiungono le regole F oppure F per○ → σ → ε, → σ → ε,ogni metasimbolo F per cui F * A; infatti risulta possibile nella grammatica la derivazione⇒​ G​F * A oppure F * A che equivale a riscrivere F come o come⇒​ ⇒

σ ⇒​ ⇒​ ε,​ σ ε.G​ G​ G​ G​ ​Possiamo a questo punto eliminare tutte le regole del tipo A B, ottenendo una grammatica di tipo→3 (G’) equivalente a G.ogni regola di produzione del tipo A con Σ è anch’essa eliminabile da una grammatica,
● → σ, σ ∈ottenendo una grammatica equivalente contenente solo regole del tipo A A Allo scopo→ σB, → ε.di eliminare regole del tipo A è sufficiente l’introduzione di un nuovo metasimbolo M e della→ σrelativa regola di produzione M sostituendo poi ogni regola di produzione del tipo A con→ ε, → σuna nuova regola di produzione del tipo A Si deduce quindi che se L è di tipo 3, allora è→ σM.generato da una grammatica di tipo 3 contenenti solo regole del tipo A A→ σB, → ε.ogni regola di produzione del tipo A è anch’essa

eliminabile da una grammatica a patto ● → ε,dell’introduzione, per ogni regola in G del tipo A dove coesiste anche la regola B → σB, → ε,aggiungere all’insieme delle regole di produzione anche la regola A si deduce quindi che se L è → σ,di tipo 3, allora è generato da G di tipo 3 contenenti solo regole del tipo A A → σB, → σ.

CAPITOLO 2: AUTOMI A STATI FINITI

SISTEMI A STATI

Esempio introduttivo: vediamo come modellare le interfacce di pagine web con gli automi

1. link che consente di andare a pagina 2 ● →l2
2. link che consente di andare a pagina 3 ● →l3
3. link consente di andare a pagina 1 ● →Rappresentazione grafica mediante il diagramma degli stati dell’automa

Automa: è un sistema schematizzabile mediante una scatola la quale acquisisce in input un messaggio su un certo alfabeto Σ e fornisce in output un risultato esprimibile sotto forma di

0/1 dove 1 significa che il messaggio è stato accettato e riconosciuto dall'automa, 0 significa che il messaggio non è stato accettato

Esperimento: è il risultato che fornisce l'automa se gli viene fornito un singolo messaggio

Viene presentata una sequenza di messaggi, descritta da w ∈ Σ* ● ∈

Al termine, viene effettuata una osservazione: se il risultato è 1 la parola viene accettata, altrimenti, nel caso in cui il risultato è 0 la parola viene respinta

Comportamento: poiché possiamo accedere al sistema solo attraverso esperimenti, il comportamento del sistema è descritto dall'insieme di parole accettate; questo sistema è quindi visto come riconoscitore di linguaggi.

Caratteristiche principali dell'automa

Un automa si compone di stati, viene indicato con "Q" l'insieme degli stati;

In ogni istante l'automa persiste in un preciso stato q ∈ Q e questo stato può

essere modificato solo● ∈attraverso un messaggio Σ inviato in ingresso;σ ∈Inizialmente l’automa deve trovarsi nello stato che prende il nome di “stato iniziale” e che si indica● con q​ , dove q​ Q, altrimenti, se l’automa non viene inizializzato, può sviluppare il cammino∈0​ 0​riconoscitivo di una parola da uno degli stati di cui si compone, si ottengono, quindi, rispostedifferenti a medesimi messaggi in ingresso in base allo stato in cui è fermo l’automa quando vienefornito il messaggio, ecco la motivazione per la quale si necessita dell’inizializzazione in q​0;Ad ogni mossa l’automa effettua la lettura di un simbolo e il relativo cambiamento di stato, la legge● che descrive la modifica di stato interno causata dall’arrivo di un messaggio è data dalla “funzione ditransizione” o anche detta “funzione di stato prossimo”, viene identificata con il

“1”

1. λ(q) = 0 se q è uno stato che serve per descrivere l’uscita “0”
2. λ(q)AUTOMA A STATI

Un a​utoma a stati ​ è un sistema descritto dalla quintupla di elementi dove:

• A =< Σ, Q, q , δ, λ ↔ F >0= alfabeto di input;
• Σ = insieme degli stati (se è finito, è a stati finiti);
• Q Q AQ = s​tato iniziale​;
• q ∈0 = f​unzione di transizione​ ;
• δ : Q × Σ →Q = f​unzione di uscita​ oppure​ = ​insieme degli stati finali
• λ : Q → {0, 1} F Q⊆

Automa come riconoscitore di linguaggi

Il linguaggio riconosciuto dall’automa A è quell’insieme di parole che soddisfano la proprietà δdell’automa. La funzione la quale indica il comportamento dell’automa alla lettura del carattereδ, σquando si trovava nello stato q, ossia Q x Σ→Q, può essere

univocamente estesa non più alla lettura δ:di caratteri Σ ma ad intere parole w Σ*, ottenendo quindi la funzione estesa dove Q x Σ*σ ∈ ∈ δ*, δ*:Q→ , w): è il codominio della funzione di transizione che definisce come cambia lo stato dell'automaδ*(q​ δ*0​in funzione della lettura della parola w Σ* partendo dallo stato iniziale q​ ,∈ 0​Descrizione di * in maniera ricorsivaδq Q, = q, ossia, lo stato in cui arriva il sistema, inizializzato con q, dopo aver● ∀ ∈ δ*(q, ε)applicato l'azione corrispondente alla lettura di nessun messaggio (ε) è uguale allo stato di inizializzazione;w Σ*, wσ) = w), ossia, lo stato in cui arriva il sistema, inizializzato con● ∀ ∈ δ*(q, δ(δ*(q, σ),q, dopo aver applicato le azioni corrispondenti alla sequenza wσ di messaggi [δ*(q, wσ)]

èequivalente allo stato in cui arriva il sistema, inizializzato con lo stato in cui è arrivato il sistemainizializzato con q, dopo aver applicato le azioni corrispondenti alla sequenza w di messaggi[δ*(q, w)=q​ ], dopo aver applicato l’azione corrispondente al simbolo [δ(q​ ,σ σ)];1​ 1​

Linguaggio riconosciuto dall’automa AL(A) = {w Σ* | w)) = 1} = insieme di tutte le parole definite su Σ tali che l’automa,● ∈ λ(δ*(q​0,partendo dallo stato iniziale e analizzando le parole fornite arrivi sempre in uno stato legato allafunzione d’uscita λ=1L(A) = {w Σ* | w) F} = insieme di tutte le parole definite su Σ tali che, se fornite alla● ∈ δ*(q​ ∈0, ​funzione di transizione, insieme allo stato di partenza q​ , la funzione di transizione porta in uno0​stato appartenente all’insieme degli stati che consentono di ottenere uscita 1Informalmente gli

induce la lettura ₁a_bb_● → → →q_{1 2 1}della stringa “abb” e termina nello stato q_F quindi non è riconosciuta∉₁“aba”? SI, q_q q_q , termina nello stato q_F quindi è riconosciuta₁a_ba_● → → →q_∈ 2 2 2“ε” è accettata dall’automa? no, infatti da q₁ , non vengono effettuate trasformazioni quindi_●