Schließung in regelmäßigen Sprachen

Question

a) Lassen Sie $ L $ eine normale Sprache sein.Nach dem Theorem gibt es ein DFA, das die Sprache akzeptiert.

beschreiben Sie in Kürze, wie Sie den DFA in NFA wechseln, der $ l ^ R $ akzeptiert, wobei R umgekehrt ist.

Es ist nicht erforderlich, aufzuschreiben, wie man formal oder Beweis oder Korrektheit aufgebaut wird.

b) true oder false: Wenn $ L $ nicht regelmäßig ist, dann $ l ^ r $ ist nicht regelmäßig

meine Lösung:

a) Zunächst einmal, weil wir umgekehrt wollen, dass der akzeptierende Zustand der Anfang werden würde, und die Ablehnungszustände werden akzeptiert, auch die Richtung der Kanten auf die entgegengesetzte Seite wechseln. Aber wenn es darum geht, es an NFA zu ändern, bin ich ein bisschen stecken.

b) Ich denke, es ist wahr, da es nicht egal ist, ob es umgekehrt ist, ob es dann regelmäßig ist, dann ist es natürlich $ l ^ R $ regelmäßig sein wird.

.

ist das für A und B?

Answer 1

a)

Zunächst einmal, weil wir umgekehrt wollen, dass der akzeptierende Zustand der Anfang werden würde, und die Ablehnungszustände werden annehmen, auch die Richtung der Kanten auf die gegenüberliegende Seite wechseln.

Du bist fast da. Was passiert, wenn Sie mehrere akzeptierende Zustände in der ursprünglichen DFA haben? Hier benötigen Sie NFA-Funktionen, um sie umzuwandeln.

Hier ist ein Spoiler, falls Sie Ihre Antwort überprüfen möchten: Entwurf eines DFA und der Rückseite davon auf ComputerScience.se .

b)

Ihre Antwort ist wahr, obwohl Sie es möglicherweise ein bisschen sorgfältiger einziehen möchten. Wir möchten beweisen, "wenn $ L $ nicht regelmäßig ist, $ l ^ r $ ist nicht regelmäßig" . Also lass $ l $ nicht regelmäßig sein. Wenn $ l ^ R $ regelmäßig waren, waren so $ (l ^ r) ^ r= l $ Das ist ein Widerspruch. Daher ist $ l ^ r $ nicht regelmäßig.