Entwerfen Sie eine Sprache L, so dass weder L noch seine Komplement eine unendliche reguläre Untergruppe haben?

Question

Ich habe eine Klasse zur Automatentheorie, und im Moment lernen wir das pumpende Lemma. Es gibt eine Übungsfrage, in der wir "eine Sprache L so entwerfen L darstellen, so dass w weder L noch seine Ergänzung eine unendliche regelmäßige Untergruppe haben?" Aber ich verstehe die Frage nicht. Was ist eine unendliche reguläre Untergruppe? Wie soll ich eine Sprache finden, die diese Anforderung erfüllen kann?

Kann jemand diese Frage Licht werfen?

Vielen Dank!

Answer 1

Genauer gesagt müssen Sie eine Sprache finden L so dass es keine Teilmenge von gibt L Das ist eine unendliche reguläre Sprache und es gibt keine Untergruppe der Komplement von L Das ist eine unendliche reguläre Sprache.

Hier ist ein falsches Beispiel: L = die Vereinigung von a^n und a^n b^n. Seit a^n ist eine reguläre Sprache und es ist eine Teilmenge von L, Dies würde nicht für die Antwort funktionieren.

Für das Finden a L Das entspricht den Anforderungen, ich habe festgestellt, dass diese Art von Fragen eher Rätseln ähneln. Sie versuchen einige Dinge aus, überprüfen, ob sie funktionieren oder nicht, und versuchen darüber nachzudenken, warum sie das Problem nicht lösen. Irgendwann haben Sie Ihre Gedanken in die Situation und entwickeln sich eine Lösung.

Answer 2

Nun, eine unendliche reguläre Untergruppe einer Sprache ist eine Untergruppe, die unendlich und regelmäßig ist. Okay, das ist wahrscheinlich nicht sehr hilfreich.

"Subset" ist also ziemlich klar.

Eine "reguläre Untergruppe" wird von einer deterministischen endlichen Zustandsmaschine akzeptiert (es gibt tatsächlich einen erstaunlichen Satz in der Theorie der Sprachen, die besagt, dass diese Bedingung einer Handvoll anderer Bedingungen entspricht).

Ein "unendlicher Satz" ist ein Satz, der nicht endlich oder gleichwertig ist, ein Satz, der unendlich viele Elemente hat.

Sagen wir also, dass eine Sprache L ist etwas Besonderes, wenn es eine unendliche reguläre Untergruppe hat.

Es ist Ihre Aufgabe, eine Sprache zu finden L so dass beide L und die Ergänzung von L sind nicht etwas Besonderes.

Um mit diesem Problem irgendwohin zu gelangen, müssen Sie zuerst Ihren Kopf um diese Definition wickeln. Nehmen Sie einige der Beispiele für Sprachen aus Ihren Notizen und Ihrem Text. Finden Sie heraus, ob sie regelmäßig sind. Wenn Sie eine finden, die nicht, überlegen Sie, was es nicht regelmäßig macht, und prüfen Sie, ob Sie eine Sprache entwerfen, die die Eigenschaft hat, dass alle unendlichen Teilmengen nicht regelmäßig sind. Dann sehen Sie, was passiert, wenn Sie sich die Ergänzung ansehen.

Sie müssen Ihre Intuition aufbauen, und der einzige Weg, dies zu tun, besteht darin, Ihre Hände schmutzig zu machen.