Automi e Regexp

Per l’analisi lessicale vogliamo cercare di ricordare le parole legali all'interno di questo linguaggio e questo è fatto con i linguaggi regolari.

Introduzione a analizzatori lessicali

Token

Struttura del token è fatto da due parti

Identificatore della classe del token
Identificatore del valore del token
Pattern e lessema ci sono direi boh

Pattern e Lessema

I pattern sono una descrizione generale della forma dei valori di una classe di token.

Lessema è una istanza di un particolare pattern

Esempio di scan

Di solito viene storato come puntatore alla tabella dei simboli

Espressioni regolari

Definizione

Slide definizione espressioni regolari
Disambiguazione della grammatica
Esempio espressione regolare

Linguaggio generato da regexp

Per capire questa parte è importante avere in mente le operazioni sui linguaggio definiti in Descrizione linguaggio

Slide

Linguaggio regolare

Definizione linguaggio regolare

Ogni linguaggio finito è un linguaggio regolare questo è una proposizione che lega fortemente i linguaggi (utilizzati poi veramente per l'implementazione) (basta fare l’unione!)

Esempio linguaggio finito generato da linguaggio regolare
Esempi di espressioni regolari infiniti

Oltre ai classici operatori definiti in precedena per questa sezione aggiungiamo

Ripetizione-positiva, Possibilità, Elenco

Definizioni regolari

Le definizioni regolari ci aiutano a creare una struttura del token di cui dobbiamo fare lo scanning.

In pratica andiamo a creare delle definizioni che rendono più facile la descrizione di un pattern con regexp.

Slide
Esempi

Equivalenza regexp

Untitled 11

Esempi di equivalenze

Queste equivalenze non sono sempre facili da dimostrare

Automi

In questa parte si fa una descrizione molto generale di cosa siano gli automi.

Caratteristiche (3)

Slide

Memoria finita (dato da un numero di stati)
Input una stringa da riconoscere
Output è solamente un singolo bit (si oppure no)

Descrizione e funzionamento

Slide

Descrizione

Testina sul primo carattere in input.
Su stato q0

Funzionamento

Il funzionamento dell'automa è molto semplice, esegue un semplice algoritmo:

Leggi il carattere attuale, se esiste una transizione etichettata con quanto letto spostati secondo la regola di quel carattere.
Dopo aver finito di leggere la stringa, se è in uno stato buono restituisci 1, altrimenti 0
Se è bloccato in uno stato ritorna 0

Diagrammi di transizione

I diagrammi di transizione sono utili per definire in modo grafico cosa fa l'espressione regolare

Slide

Automi finiti non deterministici (NFA)

Definizione (5)

Slide

Possiamo definire gli automi non deterministici come una quintupla di

(Σ, Q, q_{0} \in Q, F \subseteq Q, δ) δ : Q \times (Σ \cup ε) \to P (Q)

Albeto dei simboli di input
Stati possibili
Stato iniziale
Stati finali (accettati)
Funzioni di transizione, che ha come codominio l'insieme delle parti di Q

Alla fine, per scopi didattici si utilizza sempre il diagramma di transizione. La differenza principale con gli automi a stati finiti è che posso avere lo stesso label di transizione per singolo stato

Caratteristiche (2)

Facili da realizzare (esiste quasi una bigezione credo fra NDA ed espressione regolare)
Inefficienti (backtracking, e fallibile), principalmente causato dal suo non determinismo

Stato finale accettato

Slide

Questo è una slide molto importante per definire il concetto di stringa accettata/riconosciuta. Praticamente posso affermare che una stringa è riconosciuto da questo automa finito non-deterinistico se anche un solo cammino da q0 a un qualunque stato accettato.

Oltre questo voglio andare a definire in modo formale il concetto di mossa, o cammino in un diagramma di rappresentazione per un automa finito.

Descrizione istantanea, mossa, cammino, stringa accettata

Indico che uno stato $q$ è raggiungibile da uno stato $s$ , con il simbolo $⊢$ , ossia $s ⊢ v$ , questo è possibile solo se sto leggendo una stringa che ha come relazione una stringa buona, ma questo pezzo è più chiaro negli appunti quindi ti invito di leggere dalì con la rappresentazione logica classica.

La chiusura riflessiva e transitiva di questo concetto di mossa è indicata con $⊢_{N}^{*}$ , N è il nome di questo automa, dovrebbe essere ancora sopra. x

Linguaggio riconosciuto da NDA e equivalenza

Slide

L [N] = {w \in Σ^{*} ∣\exists q \in F, (q_{0}, w) ⊢_{N}^{*} (q, ε)}

La parte di sopra è la definizione di un linguaggio riconosciuto da un automa, è un modo molto compatto per esprire l'esistenza di un cammino come sopra.

Inoltre possiamo definire il concetto di equivalenza fra NDA che è quando il linguaggio riconosciuto è esattamente lo stesso.

Definizione di linguaggio riconosciuto con e-closure

Linguaggio riconosciuto, scritto in modo più elegante, con epsilon closure

Con la definizione di delta cappuccio possiamo definire che un linguaggio in questo modo:

w \in L [N] ⟺ \exists p \in F : p \in \hat{δ} (q_{0}, w)

NFA da espressioni regolari (!!!) (duplicato)

Questo è un teorema molto importante per rappresentare una sorta di equivalenza fra linguaggi regolari e NFA.

Enunciato
Hint dimostrazione

Induzione strutturale sulla sintassi BNF delle espressioni regolari, andremo a dimostrare che posso comporre NFA che alla fine riescono a riconoscere il linguaggio regolare
Consigli di studio

Impararsi i metodi di conversione di ogni parte della sintassi in NFA, poi li componi come dei lego e sei apposto
Dimostrazione

Automi finiti deterministici (DFA)

Definizione

Slide
Differenze rispetto NDA

Principalmente la definizione è uguale agli automi non deterministici l’unica cosa che cambia è il delta che ora è definito come

δ : Q \times Σ \to Q

Non c’è più l’insieme delle parti, magari dopo vediamo come questi automi sono equivalenti, ma c’è una esplosione esponenziale al momento di conversione da deterministico a non deterministico.