0 Daumen
1,8k Aufrufe

Hallo Community,

wie kann ich zeigen, dass diese L = { am bn cn | m, n ≤ 1 } nicht regulär ist?

Sie hat ( aufgrund vorheriger Aufgabe ) eine kontextfreie Grammatik. Meine Frage ist nun, gibt es einen eindeutigen Weg um zu zeigen, dass sie nicht regulär ist? Kumpel meinte, dass es reiche auf die Produktionen zu weisen aber das ist mir nicht sicher genug, v.A. für die Prüfung.

Ich überlegte mit Abgeschlossenheit der Regularität zu arbeiten aber fand ich es nicht gut genug um einen Widerspruch zu zeigen. Anschließend wollte ich per Pumping Lemma für Typ 3 aber mit drei Buchstaben kenne ich das gar nicht ( ausgenommen PL für Typ 2, da die L aber CFL ist, fällt das auch weg ). Welchen Weg gibt es denn hierfür?
 

Avatar von

Wie kommst du darauf, dass die Sparache kontextfrei ist? Für mich ist sie regulär. In einem Zustandsdiagramm kann man das einfach zeigen.

Verzeih, leider fügte ich das falsche Symbol, war aber dann zu spät um es zu ändern :(.
Tschakabumba erkannte meinen Tippfehler und hat mir die Antwort geliefert.
Trotzdem danke für die Antwort!

1 Antwort

+3 Daumen
 
Beste Antwort

Aloha :)

Da steht \(m,n\le1\), also ist die Sprache endlich. Jede endliche Sprache ist regulär.

Du meinst vermutlich \(m,n\ge1\)? Dann ist die Sprache tatsächlich nicht regulär. Du kannst keinen endlichen Automaten finden, der diese Sprache versteht, also gibt es auch keine reguläre Grammatik dafür. Das Problem ist, dass ein ein endlicher Automat nicht beliebig hoch zählen kann, er hat ja nur eine "endliche" Anzahl an Zuständen. Da \(n\) beliebig sein kann, können beliebig viele "b" in Folge vorkommen. Für jedes "b" müsstest du einen neuen Zustand definieren, um sicherzustellen, dass auch das zugehörige verlangte "c" gesetzt wird.

Du kannst das mit dem Pumping-Lemma begründen. Wenn ein endlicher Automat mit \(k\) Zuständen ein Wort mit mehr als \(k\) Zeichen erkennen soll, dann muss mindestens ein Zustand des endlichen Automaten doppelt besucht werden. Dann gibt es aber mindestens eine Schleife von Zuständen, die sich beliebig oft wiederholen kann. Das eigegebene Wort kann dadurch beliebig "aufgepumpt" werden.

Spätestens wenn in deinem Fall das \(n\) größer als die Anzahl der Zustände wird, verlierst der Automat die Kontrolle über die Gesamtzahl an "b", weil er nicht nachhalten kann, wie oft die entsprechende Schleife durchlaufen wird. Also ist es unmöglich, anschließend die korrekte Anzahl an "c" zu setzen.

Avatar von

Ja, ich entschuldige mich für die Verwirrung, konnte nicht mehr bearbeiten und vielen Dank für diese Antwort!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community