Reguläre Sprache

Aufrufe: 206     Aktiv: vor 4 Monaten, 1 Woche

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!

 

 

gefragt vor 4 Monaten, 3 Wochen
s
sayuri,
Student, Punkte: 108

 
Kommentar schreiben Diese Frage melden
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\}\)

geantwortet vor 4 Monaten, 1 Woche
b
buuhuuhu
Punkte: 29
 

Das stimmt wohl so nicht, denn dann wäre ja auch 001011 drin, was es nicht ist.
Außerdem ist "empty" nicht die leere Menge, sondern das leere Wort, was üblicherweise mit \(\epsilon\) notiert wird.
  ─   mikn, vor 4 Monaten, 1 Woche
Kommentar schreiben Diese Antwort melden
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.

geantwortet vor 4 Monaten, 1 Woche
m
mikn
Lehrer/Professor, Punkte: 8.31K
 

Vielen Dank für die Erklärung.   ─   sayuri, vor 4 Monaten, 1 Woche
Kommentar schreiben Diese Antwort melden