[Informatica Teorica] Algoritmo Eliminazione Degli Stati
Ciao a tutti,
ho un dubbio
Sto studiando l'algoritmo per eliminazione degli stati che permette di passare da un DFA ad una REG, tuttavia sfogliando vari appunti sparsi ho trovato che tale algoritmo permette anche "...di passare da un DFA con k stati al DFA minimale che rinosce lo stesso linguaggio.."
Sono fuso io che non capisco il "passaggio diretto" oppure intende che tale risultato è possibile grazie alla combinazione di vari algoritmi?
Grazie in anticipo
ho un dubbio
Sto studiando l'algoritmo per eliminazione degli stati che permette di passare da un DFA ad una REG, tuttavia sfogliando vari appunti sparsi ho trovato che tale algoritmo permette anche "...di passare da un DFA con k stati al DFA minimale che rinosce lo stesso linguaggio.."
Sono fuso io che non capisco il "passaggio diretto" oppure intende che tale risultato è possibile grazie alla combinazione di vari algoritmi?
Grazie in anticipo
Risposte
Ciao Arthas91 
In realtà questi due passaggi di cui parli permettono di effettuare due operazioni in senso lato analoghe. Mi spiego meglio: per un linguaggio regolare (ergo che ha una grammatica di tipo $3$ secondo la classificazione delle grammatiche di Chomsky) può sempre essere fornito un automa minimo (o minimale che dir si voglia) che lo riconosce così come un'espressione regolare che permetta di generarlo. Di fatto le espressioni regolari che rappresentano un linguaggio non è detto che siano uniche. Se ad esempio ho il linguaggio $L = \{\epsilon, a, aa, aaa, ...\}$ le espressioni regolari $L = \{a^\star \}$ e $L = \{(a^\star )^\star \}$ sono entrambe valide ai fini della rappresentazione dello stesso ma è usuale considerare soltanto la prima di queste (nella fattispecie) poiché è quella più semplice (potremmo dire "minima" prendendo però questo termine con le pinze). Potresti anche scrivere ad esempio $L = \{a^n, n \ge 0\}$ ma anche questa se ci pensi bene è più "vincolata" rispetto alla prima che invece è scritta in maniera più compatta.
Spero di averti reso l'idea, in caso chiedi pure.
In realtà questi due passaggi di cui parli permettono di effettuare due operazioni in senso lato analoghe. Mi spiego meglio: per un linguaggio regolare (ergo che ha una grammatica di tipo $3$ secondo la classificazione delle grammatiche di Chomsky) può sempre essere fornito un automa minimo (o minimale che dir si voglia) che lo riconosce così come un'espressione regolare che permetta di generarlo. Di fatto le espressioni regolari che rappresentano un linguaggio non è detto che siano uniche. Se ad esempio ho il linguaggio $L = \{\epsilon, a, aa, aaa, ...\}$ le espressioni regolari $L = \{a^\star \}$ e $L = \{(a^\star )^\star \}$ sono entrambe valide ai fini della rappresentazione dello stesso ma è usuale considerare soltanto la prima di queste (nella fattispecie) poiché è quella più semplice (potremmo dire "minima" prendendo però questo termine con le pinze). Potresti anche scrivere ad esempio $L = \{a^n, n \ge 0\}$ ma anche questa se ci pensi bene è più "vincolata" rispetto alla prima che invece è scritta in maniera più compatta.
Spero di averti reso l'idea, in caso chiedi pure.
Ciao onlyReferee,
innanzitutto grazie per la risposta, tuttavia non era quello che volevo
. So che uno stesso linguaggio L può essere rappresentato da REG distinte ma in questi appunti è più inteso come soluzione costruttiva. Cioè applicando l'algoritmo su un DFA che riconosce L, si ottiene un DFA minimale che riconosce lo stesso linguaggio. Inoltre afferma pure che se dati due automi, ottengo lo stesso automa minimale allora i due automi riconoscono lo stesso linguaggio. Io so che questo è possibile per riduzione ma volevo sapere se anche attraverso l'algoritmo di eliminazione degli stati è possibile ottenere lo stesso risultato. Se puoi aiutarmi a capire o se la motivazione è, in qualche maniera, intrinseca alla tua spiegazione illuminami T.T
Grazie mille
innanzitutto grazie per la risposta, tuttavia non era quello che volevo
. So che uno stesso linguaggio L può essere rappresentato da REG distinte ma in questi appunti è più inteso come soluzione costruttiva. Cioè applicando l'algoritmo su un DFA che riconosce L, si ottiene un DFA minimale che riconosce lo stesso linguaggio. Inoltre afferma pure che se dati due automi, ottengo lo stesso automa minimale allora i due automi riconoscono lo stesso linguaggio. Io so che questo è possibile per riduzione ma volevo sapere se anche attraverso l'algoritmo di eliminazione degli stati è possibile ottenere lo stesso risultato. Se puoi aiutarmi a capire o se la motivazione è, in qualche maniera, intrinseca alla tua spiegazione illuminami T.TGrazie mille
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo