Ausstellende einen Algorithmus, wenn L = L * bestimmt, da jede reguläre Sprache L

Question

Ich studiere Mitgliedschaft Algorithmen und ich an diesem Problem arbeite, die besagt folgende:

einen Algorithmus ausstellen dass für jede reguläre Sprache L, bestimmt, ob oder nicht L = L *

Also, mein erster Gedanke war, haben wir L *, die Kleene Stern von L ist und gut, wenn L = L *, um zu bestimmen, können wir nicht einfach sagen, dass da L regulär ist, wissen wir, L * ist definitionsgemäß die heißt es, dass die Familie von regulären Sprachen ist unter stern Verschluss geschlossen. Daher sein L immer gleich L *?

Ich fühle mich wie es ist auf jeden Fall viel mehr zu bieten, gibt es wahrscheinlich etwas, was ich bin fehlt. Jede Hilfe wäre sehr geschätzt. Nochmals vielen Dank.

Answer 1

  

da L regulär ist, wissen wir, L * per Definition ist, die besagt, dass die Familie von regulären Sprachen unter stern Verschluss geschlossen ist. Daher immer L wird auf L *?

gleich

Nein. Regular(L) --> Regular(L*), aber das bedeutet nicht, dass L == L*. Nur weil zwei Sprachen sind sowohl regelmäßige bedeutet nicht, dass sie die gleiche reguläre Sprache. Zum Beispiel a* und b* sind beide regulären Sprachen, aber das macht sie nicht die gleiche Sprache machen.

Ein Beispiel für L != L* wäre die Sprache L = a*b* und damit L* = (a*b*)*. Der String abab ist Teil L* aber nicht Teil L.

Soweit ein Algorithmus geht, möchte ich daran erinnern, dass das Konzept einer regulären Sprache ist eine, die von einem DFA analysiert werden kann - und für jede gegebene DFA, gibt es eine einzige optimale Reduzierung von, dass DFA

Answer 2

Die Implikation, dass Sie falsch angegeben ist. Verschlossen unter dem Kleene Stern bedeutet nur, dass L * ist wieder regelmäßig, wenn L regulär. Eine Möglichkeit, zu prüfen, ob L = L * ist der minimalen Automaten für beide zu berechnen und dann auf Äquivalenz zu überprüfen.