Esporre un algoritmo che determina se L = L *, dato alcuna linguaggio regolare L

Question

Sto studiando gli algoritmi di appartenenza e sto lavorando su questo particolare problema, che dice quanto segue:

Esporre un algoritmo che, dato un qualsiasi linguaggio regolare L, L determina se o no = L *

Quindi, il mio primo pensiero è stato, abbiamo L * che è Kleene stella di L e per determinare se L = L *, così non potremmo solo dire che da L è regolare, sappiamo L * è per definizione che afferma che la famiglia di linguaggi regolari è chiusa sotto star-chiusura. Pertanto L sarà sempre pari a L *?

mi sento come se c'è sicuramente molto di più ad esso, probabilmente c'è qualcosa che mi manca. Qualsiasi aiuto sarebbe apprezzato. Grazie ancora.

Answer 1

  

L poiché è regolare, sappiamo L * è, per definizione, in cui si afferma che la famiglia di linguaggi regolari è chiuso sotto stella-chiusura. Pertanto L sarà sempre pari a L *?

No. Regular(L) --> Regular(L*), ma questo non significa che L == L*. Solo perché due lingue sono entrambi regolari non significa che essi sono il stesso linguaggio regolare. Per esempio, a* e b* sono entrambi linguaggi regolari, ma questo non li la stessa lingua fa fare.

Un esempio di L != L* sarebbe la L = a*b* lingua, e quindi L* = (a*b*)*. Il abab stringa è parte di L*, ma non fa parte della L.

Per quanto riguarda un algoritmo va, lasciate che vi ricordi che il concetto di un linguaggio regolare è uno che può essere analizzato da un DFA - e in ogni dato DFA, c'è una sola riduzione ottimale di quella DFA

Answer 2

L'implicazione che lei ha affermato è sbagliato. Closedness sotto i mezzi stelle Kleene soltanto che L * è di nuovo regolare, se L è regolare. Una possibilità per verificare se L = L * è quello di calcolare l'automa minimo per entrambi e poi controllando per equivalenza.