Wikiversità

Automi riconoscitori ed espressioni regolari: differenze tra le versioni

Naviga nella cronologia in modo interattivo
← Differenza precedenteDifferenza successiva →
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
Correzioni con wikEd
Annullata la modifica 116643 di Samuele2002 (discussione) è andato insieme tutto il latex
Riga 1:
{{risorsa|tipo=lezione|materia1=Linguaggi formali e automi|avanzamento=50%}}
 
Lo scopo di questa lezione è presentare alcuni metodi per tradurre un'[[Linguaggi ed espressioni regolari|espressione regolare]] in un automa a stati finiti. Non esiste un metodo preciso e unico per effettuare questa operazione; i differenti algoritmi producono soluzioni diverse, alcuni deterministici altri no, altri con epsilon mosse altri no.
 
Introduciamo dapprima la classe dei linguaggi locali, che tornerà utile per alcuni algoritmi.
 
== Linguaggi locali ==
 
Definiamo la classe dei linguaggi localmente testabili, chiamata anche semplicemente locale ('''LOC''') come sotto famiglia (propria) dei linguaggi regolari <math>LOC \subset REG,\ LOC \not\equiv REG</math>. Per definirla facciamo uso delle seguenti "funzioni" di un linguaggio:
* insieme dei caratteri iniziali: <math>Ini(L) = \left\{\ a\in\Sigma\ |\ a\Sigma^* \cap L \ne \varnothing \right\}</math>
 
* Insiemeinsieme dei caratteri inizialifinali: <math>IniFin(L) = \left\{\ a\in\Sigma\ |\ a\Sigma^*a \cap L \ne \varnothing \right\}</math>
* Insiemeinsieme deidi caratteri finalidigrammi: <math>FinDig(L) = \left\{\ ax\in\Sigma^2\ |\ \Sigma^*ax\Sigma^* \cap L \ne \varnothing \right\}</math>
* Insiemeinsieme complemento di digrammi: <math>\overline{Dig}(L) = \left\{\ x\in\Sigma^2\ |\setminus \Sigma^*x\Sigma^* \cap Dig(L \ne \varnothing \right\})</math>
* Insieme complemento di digrammi: <math>\overline{Dig}(L) = \Sigma^2 \setminus Dig(L)</math>
 
Le operazioni sopra possono essere applicate con lo stesso effetto alla singola stringa anzichè a un intero linguaggio.
 
=== Esempi ===
: <math>EL_1=(x|yyabcd)^*(xz)^+</math>▼
 
: <math>L_1=Ini(abcdL_1)^*=\{a\}</math>
: <math>IniFin(L_1)=\{ad\}</math>
: <math>FinDig(L_1)=\{dab,bc,cd,da\}</math>
: <math>Dig(L_1)=\{ab,bc,cd,da\}</math>▼
 
: <math>L_2=a^*b^*(cd)^+</math>
: <math>Ini(L_2)=\{a,b,c\}</math>
: <math>Fin(L_2)=\{d\}</math>
: <math>Dig(L_2)=\{aa,ab,bb, ac, bc,cd\}</math>
 
: <math>Xx=abc</math>
: <math>Ini(x)=a</math>
: <math>Fin(x)=c</math>
: <math>Dig(x)={ab,bc}</math>
 
=== Definizione ===
 
Un '''lingaggio locale''' è un linguaggio che contiene tutte e solo le stringhe che possono essere generate a partire dai tre insiemi visti sopra:
: <math>L \setminus \varepsilon = \{ x\ |\ Ini(x)\in Ini(L) \and Dig(x)\subseteq Dig(L) \and Fin(x)\in Fin(L) \}</math>▼
 
▲: <math>L \setminus \varepsilon = \{ x\ |\ Ini(x)\in Ini(L) \and Dig(x)\subseteq Dig(L) \and Fin(x)\in Fin(L) \}</math>
 
Esempio1: <math>L_1=(abcd)^*</math> è locale: tutte le stringhe ottenute da Ini, Fin e Dig sono contenute in <math>L_1</math>.
Line 43 ⟶ 39:
Esempio2: <math>L_1=(bb)^*c^+</math> non è locale: la stringa ''bbbc'' non è contenuta in <math>L_1</math> ma rispetta le condizioni sopra citate.
 
Per ogni <math>L</math> regolare non locale, esiste un altro linguaggio <math>L_{LOC}</math> regolare e locale che contiene tutte le stringhe ottenibili da <math>Ini(L), Fin(L), Dig(L)</math>.
 
=== Riconoscitore ===
 
Il riconoscitore dei linguaggi locali è molto semplice: devo verificare che il primo e ultimo carattere sia quelli cercati e che ogni coppia sia presente.
 
Vediamo come fare con un esempio, traduciamo il linguaggio locale: <math>L_e=(abc)^+</math>
▲: <math>DigIni(L_1L_e)=\{ab,bc,cd,daa\}</math>
 
: <math>IniFin(L_e)=\{ac\}</math>
: <math>FinDig(L_e)=\{cab,bc,ca\}</math>
: <math>Dig(L_e)=\{ab,bc,ca\}</math>▼
 
[[File:Local-automata.png|center]]
Line 60 ⟶ 54:
 
Tra i molti metodi possibili, abbiamo:
 
* Metodo di '''Thompson''' o '''strutturale''': l'automa generato è in generale non deterministico e con <math>\varepsilon</math>-mosse.
* Metodo '''GMY''' (Glushhkov, Mc Naugthon and Yamada): l'automa generato è in generale non deterministico ma senza <math>\varepsilon</math>-mosse.
Line 66 ⟶ 59:
 
=== Metodo di Thompson ===
 
L'idea del metodo Thompson è elaborare le varie componenti l'automa partendo dalla RE e analizzandola parte per parte. Successivamente le componenti verranno interconnesse in modo da ottenere un riconoscitore completo.
 
Line 80 ⟶ 72:
 
[[File:Thompson-a-symbol.svg|center]]
 
 
L''''espressione ottenuta dall'unione di due sottoespressioni <math>e=s|t</math>''' è convertita da
 
[[File:Thompsonthompson-or.svg|center]]
 
Lo stato <math>q</math> va tramite un' <math>\varepsilon</math>-transazione in uno stato iniziale di <math>N(s)</math> o <math>N(t)</math>. I loro stati finali divengono intermedi e si uniscono per mezzo di <math>\varepsilon</math>-transazioni nello stato finale di N(e) chiamato <math>f</math>.
Line 89 ⟶ 82:
L'espressione formata dalla concatenazione di due sottoespressioni <math>e=st</math> si converte con
 
[[File:Thompsonthompson-concat.svg|center]]
 
Lo stato iniziale di <math>N(s)</math> è lo stato iniziale di N(e). Lo stato finale di <math>N(s)</math> diventa lo stato iniziale di <math>N(t)</math>. lo stato finale di <math>N(t)</math> è anche lo stato finale di <math>N(e)</math>.
 
La [[w:Kleene star|Kleene star]] di un'espressione <math>e=s^*</math> è convertita da
 
[[File:Thompsonthompson-kleene-star.svg|center]]
 
Un' <math>\varepsilon</math>-transizione connette lo stato iniziale e finale dell' NFA <math>N(e)</math>. Un'altra <math>\varepsilon</math>-transizione che va dallo stato finale a quello iniziale di <math>N(s)</math> consente la ripetizione dell'espressione <math>s</math> come da definizione dell'operatore Kleene star.
Line 103 ⟶ 96:
 
=== Metodo BS ===
 
Per il metodo BS sfrutteremo i linguaggi locali definiti nella prima sezione. Ricordiamo che il grande vantaggio di questo metodo è che l'automa generato è deterministico. Introduciamo questo algoritmo tramite un esempio.
 
Si prenda la seguente RE:
▲: <math>Dige=(L_ex|yy)=\{ab,bc,ca\}^*(xz)^+</math>
 
▲: <math>E=(x|yy)^*(xz)^+</math>
 
e la sua versione numerata terminata (ovvero con un carattere alla fine chiamato terminatore <math>\dashv</math>):
: <math>Ee'=(x_1|y_2y_3)^*(x_4z_5)^+\dashv</math>▼
 
▲: <math>E'=(x_1|y_2y_3)^*(x_4z_5)^+\dashv</math>
 
Definiamo insieme dei successori di un carattere come segue:
: <math>Fol(a_i)\ :=\ \{\ b_j\ |\ a_ib_j\in Dig(e')\ \}</math>▼
 
▲: <math>Fol(a_i)\ :=\ \{\ b_j\ |\ a_ib_j\in Dig(e')\ \}</math>
 
Risulterà quindi che il terminatore è il carattere che segue tutti i caratteri finali
:<math>\dashv \in Fol(a_i),\ \ \forall a_i \in Fin(e')</math>
 
: <math>\Dashv \in Fol(a_i\dashv),\ \= \forall a_i \in Fin(e')varnothing</math>
: <math>Fol(\dashv) = \varnothing</math>▼
 
(abbiamo usato un abuso di notazione, il carattere terminatore non è propriamente parte della RE, altrimenti sarebbe da considerare il finale)
 
:: Nel precedente esempio risulterà: <math>Fol(x_1) = \{x_1,y_2,y_4\}</math>, <math>Fol(y_2) = \{y_3\}</math>, <math>Fol(z_5) = \{x_4, \dashv \}</math>, ...
Ogni insieme <math>Fol()</math> corrisponde all'insieme dei simboli che si aspettano come prossimo input e il terminatore rappresenta lo stato finale. Di conseguenza lo stato iniziale risulta: <math>Ini(e'\dashv)</math>.▼
 
▲Ogni insieme <math>Fol()</math> corrisponde all'insieme dei simboli che si aspettano come prossimo input e il terminatore rappresenta lo stato finale. Di conseguenza lo stato iniziale risulta: <math>Ini(e'\dashv)</math>.
 
Si applica in seguente algoritmo:
▲: <math>FolQ = Ini(e' \dashv) = \varnothing</math>
 
: <math>Q\delta = Ini(e' \dashv)varnothing</math>
:<math>\textbf{WHILE} \text{ esiste uno stato } q\in Q \text{ non visitato } \textbf{DO}</math>
: <math>\delta = \varnothing</math>
: :<math>\Textbf{WHILE} \text{ esiste uno statosetta } q\in Q \text{ non visitato } \textbf{DO}</math>
:: <math>\Texttextbf{settaFOREACH} \text{ simbolo } qb\in \Sigma \text{ visitatoterminale } \textbf{DO}</math>
:: :<math>q' = \Textbfbigcup_{FOREACH} \text{forall simbolo } bb_i\in \Sigma \text{ terminale q} \textbf{DO}Fol(b_i)</math>
::: <math>Q\textbf{IF}\ q' =\ne \bigcup_{varnothing\forall b_i\in qtextbf{THEN} Fol(b_i)</math>
::: :<math>\Textbftextbf{IF}\ q' \nenotin \varnothingQ\ \textbf{THEN}</math>
:::: :<math>\Textbftext{IFsetta }\ q' \notintext{ Q\NON visitato \textbf{THEN}</math>
::::: <math>\Text{settaQ }= q'Q \text{cup NON visitato }q'</math>
::::: <math>Q = Q \cuptextbf{END q'IF}</math>
:::: <math>\Textbfdelta = \delta \cup {ENDq \overset{b}{\to} IFq'}</math>
:::: <math>\delta = \delta \cup textbf{q \overset{b}{\to}END q'IF}</math>
::: <math>\Textbftextbf{END IFDONE}</math>
:: <math>\Textbftextbf{DONE}</math>
: <math>\Textbf{DONE}</math>
 
L'algoritmo BS può anche essere usato per rendere un automa deterministico, anche se l'automa non deterministico di partenza possiede <math>\varepsilon</math>-mosse. L'idea è la seguente:
# Sisi ottiene una versione numerata dell'automa, aggiungendo anche un numero ad ogni <math>\varepsilon</math>-mossa;▼
 
# Sisi calcolino similmente alle regex gli insieme Ini e Fol;▼
▲# Si ottiene una versione numerata dell'automa, aggiungendo anche un numero ad ogni <math>\varepsilon</math>-mossa;
# Utilizzandoutilizzando BS si ottenga il nuovo automa deterministico.▼
▲# Si calcolino similmente alle regex gli insieme Ini e Fol;
▲# Utilizzando BS si ottenga il nuovo automa deterministico.
Estratto da "https://it.wikiversity.org/wiki/Automi_riconoscitori_ed_espressioni_regolari"