Reguläre Sprache

Aufrufe: 966     Aktiv: 26.07.2020 um 11:25
0

Hallo zusammen

Ich weiss gerade nicht, ob ich diese Frage hier überhaupt stellen kann.  Leider verstehe ich die reguläre Sprache überhaupt nicht, als ich die untenstehende Aufgabe sah, wusste ich nicht, wie ich am besten Vorgehen soll, um aufzuzeigen, dass es sich entweder um eine reguläre Sprache handelt oder nicht.

 

B = {0^n1^n | n >= 0} = {empty, 01, 0011, 000111, . . .}

Warum ist es keine reguläre Sprache oder andersherum gefragt, was sind die typische kennzeichen für eine reguläre Sprache?

 

Vielen Dank für eure Antworten!

 

 

Diese Frage melden
gefragt

Student, Punkte: 205

 
Kommentar schreiben
2 Antworten
0

Wie du zeigst, dass es sich hier um keinen regulären Ausdruck handelt, kann ich dir leider auch nicht sagen. Deine Menge könnte man mit Hilfe von regulären Ausdrücken aber so darstellen:

\( \{ \emptyset \} \cup \{0(01)^*1\}\)

Diese Antwort melden
geantwortet

Punkte: 29

 

Kommentar schreiben

0

Man kann mit dem pumping lemma (das bei einer regulären Sprache erfüllt sein müsste) beweisen, Die Idee ist, dass man in ein Wort aus L beliebig viele 0 reinpumpen könnte (wäre L regulär), was aber zu einer unterschiedlichen Anzahl von 0 und 1 in einem Wort führen würde (das also nicht in L liegt).

Hier findest Du den ausführlichen Beweis:

https://de.wikipedia.org/wiki/Pumping-Lemma#Beispiel

Im Beispiel dort ist \(m\ge 1\) (bei dir oben \(\ge 0\), spielt aber für den Beweis keine Rolle.

Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 38.86K

 
Vielen Dank für die Erklärung.   ─   sayuri 26.07.2020 um 11:25

Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden. Mikn wurde bereits informiert.