Linguaggi liberi e PDA

In questa parte del nostro percorso nei linguaggi di programmazione proviamo ad espandere NFA e DFA in modo che possano riconoscere linguaggi come $w{w}^r|w\in \{a,b{\}}^{\ast }$ , con r maggiore o uguale a zero (r per dire che è il contrario di w) (questo linguaggio per il pumping lemma).

Grammatiche libere da contesto

Conosciute come context-free grammars, possiamo definirle in modo matematico come una tupla

$$G=⟨\mathcal{N},S,\Sigma ,\mathcal{R}⟩$$

Dove $\mathcal{N}$ sono i non terminali, $S$ è il non terminale iniziale, $\Sigma$ sono l'alfabeto dei simboli finali e $\mathcal{R}$ le relazioni possibili. Spesso lo scriviamo solo tramite le relazioni, perché è la forma più compatta. I nodi di una derivazione da grammatica libera da contesto è chiamato costituente del linguaggio. Questo è più importante in linguistica.

Push-down automata

Introduzione automi a pila (7)

L'idea principale per espandere gli NFA è il concetto di stato o memoria, avere quindi una stack o pila può rendere molto più espressivo queste entità.

Il prof. definisce automa a pila non deterministico (PDA) questa settupla $(\Sigma ,Q,\Gamma ,\delta ,q_0,\perp ,F)$

• $\Sigma$ l'alfabeto finito dei simboli in input
• $\Gamma$ l'alfabeto dei simboli sulla pila
• $Q$ l'insieme degli stati
• $\delta$ transizione, nella forma $\delta :Q\times (\Sigma \cup \left\{\epsilon \right\})\times \Gamma \to \mathbb{P}(Q\times {\Gamma }^{\ast })$
• $q_0$ lo stato iniziale
• $\perp \in \Gamma$ il simbolo iniziale sulla pila
• $F\in Q$ l'insieme degli stati finali. Una differenza che fa questo prof. contro La macchina di Turing è che lui fa distinzione dei simboli sulla pila, mentre l'altro no, una altra differenza è che gli stati finali sono esterni nell'altro. Ma credo alla fine sia equivalente.

Attenzione: l'automa può leggere qualcosa solo se la sua stack non è vuota!

La parte inteessante dei PDA rispetto agli automi studiati in Automi e Regexp è la funzione di transizione, che è ora nella forma

$$\delta :Q\times (\Sigma \cup \{\epsilon \})\times \Gamma \to P(Q\times {\Gamma }^{\ast })$$

• Esempio hard di PDA

Computazione automi a pila

![[image/universita/ex-notion/Linguaggi liberi e PDA/Untitled 7.png]]

Accettazione della stringa

La cosa particolare degli automi a pila è che accettano la stringa anche quando la pila diventa vuota, non solo quando finisco di leggere e ho uno stato che è bello. Ossia detto meglio, posso costruirmi un automa a Pila che accetta la stessa stringa quando la pila diventa vuota, c'è una sorta di equivalenza fra stato e cose sulla pila.

• Slide

  

La cosa importante da capire per questa parte è che si differenziano due metodi di accettazione per la stringa:

1. Pila vuota
2. Stato finale.

In entrambi i casi devo leggere tutto l'input, e poi vado a vadere dove sto. Nel primo caso se ho letto tutto l'input e la pila è vuota allora accetto, nel secondo caso se ho letto tutta la stringa e sono in uno stato finale allora vado ad accettare.

Teorema equivalenza accettazione Vuoto-Stato

• Enunciato

  

• Dimostrazione in slide

  

L'idea dietro questo teorema è molto simile a quanto presente nella conversione fra espressione regolare e NFA, perché sto andando in modo ricorsivo, supponendo che ho già un vecchio automa che funzioni, e basta che ci costruisca cose intorno ad essa. (in questo caso simbolo iniziale nuovo e stato finale che più o meno racchiude tutti gli stati finali!

Z è un simbolo stack nel nostro nuovo automa, solo utilizzato per gestire meglio alcune cose con la stack.

Ogni linguaggio è libero sse riconosciuto da PDA (chiede)

• Enunciato

  

• Dimostrazione

  

  

  

  

• Diagramma PDA per →

  Nota questo non è il PDA di cui parlava il prof nelle slides, bisognerebbe condensarlo in un unico stato. Questo qui risolve per stato finale, quello del prof per stack vuota

  

Note sulla dimo

Vogliamo dimostrare un sse, in una proviamo a costruire un automa partendo dalle regole della grammatica, (non dimostriamo che l'automa riconosce effettivamente, la costruiamo ebbasta.

Per l'altra freccia bisogna avere dimostrato prima alcuni lemmi che noi saltiamo per ora.

Proprietà dei linguaggi liberi

Unione, Conc, e Kleene

• Dimostrazione

  

In pratica i non terminali e terminali sono uniti assieme, e con qualche produzione in più sullo stato iniziale per gestire le cose.

Intersezione con linguaggio regolare (chiede per alto voto)

Questa è qualcosa di leggermente più tosta, però in soldoni sto facendo un bruteforce, e prendendo tutte le combinazioni possibili per cui si possa riconoscere

• Th e dimostrazione

  

Con questo teorema è spesso utile per dimostrare che un linguaggio non è libero.

Invece non sono chiusi per intersezione i linguaggi liberi

• Esempio di non chiusura

  

Da questo dato si può concludere che non sono chiusi per complemento altrimenti lo sarebbero anche per l'intersezione.

Pumping theorem, tosta (!)

• Enunciato

  

• Dimostrazione

  

  

  

  

  

  

  

• Dimostrazione libro sispser (più chiaro)

  

  

L'idea è sempre avere così tanti stati che avrò per forza dei non terminali duplicati. uno sotto l'altro, in una forma ricorsiva, allora prendo il minore e vado a fare ragionamenti lì.

Classificazione dei linguaggi

Classificazione di Chomsky

Chomsky, linguista, ha descritto una gerarchia di linguaggi

• Caratterizzazione dei linguaggi

Sulla decidibilità guardare Fondamenti teorica e La macchina di Turing

In questo caso i nuovi sono

• Grammatiche dipendenti dal contesto, in cui una singola produzione può avere più non-terminali.
• Grammatiche motonone, le cui produzioni basta che crescano
• Grammatiche generali, in cui non c'è nessun vincolo di produzioni

Schema generale delle grammatiche

Per turing, vedere La macchina di Turing.

Gerarchia automi

In generale si può estendere dicendo

• Automi Limitati riconoscono grammatiche dipendenti dal contesto
• Automi di Turing riconoscono i linguaggi ricorsivi, e sono in grado di enumerare ricorsivamente quelle generali. (anche se è semidecidibile, quindi forse non riesce a ricononscerli tutte??)