Grammatiche Regolari

Introduzione

Definizione grammatica regolare 🟩

• Definizione

  

In pratica posso avere solamente come terminali a, oppure un suffisso a su un non terminale.

Queste grammatiche sono interessanti perché è molto facile costruire un automa che sia in grado di riconoscere questo linguaggio.

Seguendo una definizione più lasca possono anche accettare dei nonterminali epsilon

Espressione regolare a NFA 🟩

Questa sezione è anche presente in Automi e Regexp, però è riportata qui così c’è l’insieme di tutte le cose in un unico posto.

• Enunciato

  

• Dimostrazione

  Mi creo un automa che riconosce in modo ricorsivo (per tutte le produzioni della grammatica delle regexp

  

  Guarda lezione 7

Da grammatica regolare a NFA (!) 🟩

In modo simile a quanto si fa per la dimostrazione per espressioni regolari rappresentabili come NFA anche questa è così

• Dimostrazione

  

Da DFA a grammatica regolare 🟩

Questo è anche conosciuto come algorithmo di Kleene.

• Dimostrazione

  

Grammatica regolare a linguaggio regolare 🟩

• Dimostrazione molto informale

  

Praticamente l’idea principale è fare rimpiazzamenti ricorsivi finché non lo ho in una forma bella.

• Riassunto tutte le equivalenze NFA, DFA, grammatiche ed espressioni.

  

Riassunto delle equivalenze 🟩-

C’è una precisa domanda che chiede di discutere in modo generale le equivalenze, quindi metto anche questo doc.

• Slide

  

Costruzione dello scanner

Introduzione 🟩

• Slide

  

Per fare questa cosa rientra il problema di creazione della DFA da NFA più piccola possibile!.

Non so come si faccia, ma almeno ora sai che esiste questo problema.

Ad intuito possiamo andare ad affermare che un automa è minimo quando non ci sono due stati equivalenti ossia, sempre ad intuito, non li possono compattare in uno, quindi non ho ridondanza di stati.

• Esempio di minimizzazione

  

Equivalenza ed indistiguibilità (di stati) 🟩

• Slide

  

Ossia se due stati sono in grado di riconoscere esattamente lo stesso linguaggio, sono equivalenti. Ma ogni stringa del linguaggio è una cosa difficile da gestire, per questo motivo provo a dimostrare che non siano equivalenti, ossia lo stato di accettazione per una stessa stringa sia diversa partendo dalla stringa vuota

• Slide strategia

  

Provo a togliere tutti

Famiglia di relazioni (5) 🟩-

• Slide

  

In pratica sto andando a guardare se lo stato finale è lo stesso o meno, partendo dalla stringa nulla, poi andando avanti a costruire altre, e continuando a togliere se lo stato finale ora è diverso.

Questa è una relazione di equivalenza.

• Proprietà

  

Dimo proprietà 4, se non cambia ho finito 🟨

Ossia se non tolgo più coppie in un passo, allora il mio algoritmo dovrà essere finito.

• Dimostrazione

  

• Esempio di applicazione dell’algoritmo di minimizzazione

  

Minimizzazione

In questa parte andremo a trattare definizioni e algoritmi utili a minimizzare un automa DFA (nel senso di meno stati possibili).

Algoritmo degli stati equivalenti 🟩

• Algos

  

Praticamente vado a marcare per tutte le cose possibili (partendo dalla relazione 0). Vado a marcare se non appartengono alla stessa relazione di equivalenza (ossia sono diversi). E se i percorsi più lunghi finiscono su altre celle già occupate, allora marco anche questo, con un segno diverso, per dire che non sono equivalenti per un certo percorso più lungo.

Dimostrazione correttezza algoritmo 🟨+

• Enunciato di terminazione e correttezza dell’algoritmo

  

• Dimostrazione di sopra

  

Terminazione è dipendente dalla proprietà 4 a 5, cioè che se non cambia a un passo, allora non cambia a nessun passo, e la 5 che mi dice che ad ogni passo ne marco almeno uno (e questi sono numeri finiti).

Distinguibilità se la casella marcata allora esiste un percorso che termina in modo diverso da uno rispetto all’altro, in altro termine esiste una stringa che è riconosciuta da uno ma non è riconosciuta da un altro! (ma se lo ho marcato in questo modo allora è ovvio che succeda questo!).

Automa minimo (4) 🟩

Questa definizione tratta le caratteristiche formali di un automa minimo costruito da un DFA valido.

(minimizzare gli stati, la funzione di transizione e gli stati accettati).

In pratica nello stesso stato dell’automa minimo ci metto tutti gli stati equivalenti ad essa, in questo senso di minimo!

• Definizione

  

Probabilmente in questo passo intendevo sono 3 le cose nuove differenti

1. Stati possibili devono essere gli equivalenti fra tutti.
2. Transizioni è ora fatto su stati equivalenti
3. Stato iniziale è la classe di equivalenza sullo stato iniziale
4. Gli stati accettati sono le classi si equivalenza sugli stati finali..
5. Alfabeto è lo stesso.

Equivalenza automa minimo e originale (non chiede) 🟨—

• Slide linguaggio riconosciuto è lo stesso, ed è anche il minimo

  

• Dimostrazione

  

In pratica per dimostrare il minimo suppongo che esista un automa con ancora meno stati, questi due (il minimo nuovo e il minimo costruito) devono riuscire a riconoscere esattamente le stesse cose, ma essendo questo con ancora meno, deve essere che il minimo costruito abbia due stati equivalenti, cosa che non può succedere col nostro algoritmo

Lex/Flex e Yacc

Questi sono analizzatori lessicali che prendono in input un file di definizioni regolari e restituisce un programma in C che riesca a riconoscere questi automi

• Diagramma semplificativo di quanto fa

  

Struttura di file Lex (3) 🟩

• Slide riassunto

  

Dichiarazioni

Praticamente in sta parte ci sono le definizioni regolari che abbiamo discusso più sopra nello stesso documento che ci rende la scrittura di espressioni regolari molto più semplice

Regole

Qui definisci tutte le espressioni regolari che ti servono. Definite in schema di

Pattern → azione

Ossia se un pattern è riconosciuto, esegui una azione.

Funzioni ausiliarie

Nel caso in cui le azione sono tropp complesse una serie di funzioni ausiliare possono essere molto utili

Funzionamento di Lex (4) 🟨+

In questa parte descriviamo brevemente le regole che il lex utilizza per decidere cosa fare.

1. Matcha seguendo le regole
   1. A parità di matching diversa, sceglie quello il matching più lungo
   2. A parità di lunghezza di matching, sceglie quello listato prima
2. Se non matcha, viene dato in output la stringa inalterata
3. Esistono funzioni per gestire i match, la stringa matchata, la lunghezza della stringa matchata (yytext e yylenght)
4. Esistono funzioni per matchare di più o di meno, come yymore e yyless.

Yacc 🟩

A differenza di Lex, Yacc si occupa di generare la sintassi.

Questo è un analizzatore sintattico, quindi sarà trattato nel dettaglio in un capitolo successivo. Per ora basta capire che i processi di scanning e parsing sono eseguiti più o meno in parallelo, è il parser che chiede ogni volta il token, evitando di avere in memoria rappresentazioni differenti della stessa cosa.

yylval sono variabili comuni che permettono di scambiare informazioni.

yylex() è cchiamato da yacc nel momento di richiesta di lessemi

Pumping Lemma (!!!) 🟩

• Enunciato

  

• Dimostrazione

  

• Negazione del pumping lemma

  

Proprietà dei linguaggi regolari (5) 🟩

1. unione
2. concatenazione
3. stella di Kleene
4. Complemento
5. Intersezione

• Dimostrazione