Reguläre Sprache durch regulären Ausdruck darstellen

Question

Frage:

Entscheiden Sie, ob die Aussage richtig oder falsch ist. Begründen Sie Ihre Entscheidung.

Die Sprache \(\{L = \{a^nvv^Rb^m | n, m \in \mathbb{N}, n, m \geq 0, v \in \{c,d\}^*\}\) ist regulär.

Mein Ansatz:

Wenn die Sprache L regulär wäre, müsste man sie durch einen regulären Ausdruck darstellen können.

Ich kam auf folgendes Ergebnis: r = a*(c + d)*b*

1) Ist dieser reguläre Ausdruck richtig?

2) Bei (c+d)*, da bedeutet das +Zeichen doch, c ODER d beliebig, oder? Oder heißt es Und?

LG

Comments

Ich habe auch noch eine weitere Frage.

Bei der Sprache L = (((b+c)* + a*) a (b+c)*)

wieso ist w = baab nicht in der Sprache? (b+c)* heißt doch b* oder c* oder beides*, oder nicht? Also darf doch b oder c auch einzeln auftauchen, oder heißt das +, dass wenn sie auftauchen, dann immer nur beide zusammen?

---

L = {a^nvv^Rb^m | n, m ∈ ℕ, n, m ≥ 0, v ∈ {c,d}*

Es ist nicht zu entziffern, was du damit meinst. Was macht das v im Exponenten. Wo kommt das R her? Das ^ im Exponenten kommt mir ebenfalls seltsam vor. Außerdem fehlt eine Klammer.

---

a hoch n v v(reverse) b hoch m

So ist es gemeint. R steht für reverse. Ich dachte, das wäre allgemein bekannt und nicht bei jedem prof unterschiedlich. Entschuldigung

---

Ich habe das in meine Antowrt eingebaut.

Answer 1

\(\{L = \{a^nvv^Rb^m | n, m \in \mathbb{N}, n, m \geq 0, v \in \{c,d\}^*\}\)

Die Sprache ist nicht regulär, weil Automaten nur einen endlichen großen Speicher haben.

Ein Automat, der \(L\) erkennt, muss sich das Wort \(v\) merken, um zu entscheiden, ob anschließend \(v^\mathrm{R}\) gelesen wurde. Das Wort \(v\) kann aber beliebig lang sein. Also wird ein unendlich großer Speicher benötigt.

Ich kam auf folgendes Ergebnis: r = a*(c + d)*b*

Das Wort \(c\) passt auf diesen regulären Ausdruck obwohl \(c\notin L\) ist.

L = (((b+c)* + a*) a (b+c)*)

Wörter aus L

1. beginnen mit einem (b+c)* oder einem a*
2. gefolgt von einem a
3. gefolgt von einem (b+c)*

wieso ist w = baab nicht in der Sprache?

Das Wort baab

1. beginnt mit einem b, wozu (b+c)* oder a* passt

   N.B. das Wort ba passt nicht auf ((b+c)* + a*)

2. gefolgt von einem a
3. gefolgt von einem a, wozu (b+c)* nicht passt.

2) Bei (c+d)*, da bedeutet das +Zeichen doch, c ODER d beliebig, oder?

Maßgeblich für die Bedeutung von Zeichen sind die Definitionen in deinen Unterlagen. Lerne, diese zu nutzen! Ich habe oben das + als ODER verwendet, weil das deiner Vermutung entspricht.

Comments

Hallo Oswald,

zu deiner Antwort: "Die Sprache ist nicht regulär, weil Automaten nur einen endlichen großen Speicher haben."

habe ich folgende Frage:

Bei der Sprache L = {vv^R | v ∈ {a}*}, habe ich bei der Fragestellung, ob die Frage regulär sei, folgende Musterlösung:

Die Sprache L ist regulär, denn sie kann durch folgenden regulären Ausdruck ausgedrückt werden: (aa)*.

Hier ist es doch aber der gleiche Fall, wie du ihn schilderst. v könnte auch unendlich sein. Oder übersehe ich etwas?

---

Bei der Sprache L = {vv^R | v ∈ {a}*},

Da ist jeder Buchstabe von \(v\) ein \(a\). Also besteht \(vv^\mathrm{R}\) ausschließlich aus einer geraden Anzahl von \(a\)s. Um das zu prüfen ist kein unendlich großer Speicher notwendig.

In deiner ursprünglichen Frage ist aber \(v\in \{c,d\}^*\). Da ist eine Vereinfachung wie bei \(v\in \{a\}^*\) nicht möglich.

---

Danke dir!

Oswald,

in meinen Unterlagen ist (r+s) die Vereinigung.

Aber wenn wir z.B. bei einem indeterminierten endlichen Automaten den Zustand A haben, und ein Pfeil auf sich selbst, mit (a,c), wieso wird das dann in den regulären Ausdruck (a+c) umgewandelt?

Der Pfeil a,c bedeutet doch, es kann a, oder c, oder beides.

Und (a+c) ist doch die Vereinigung also MUSS beides gleichzeitig vorkommen, oder nicht?

---

den Zustand A haben, und ein Pfeil auf sich selbst, mit (a,c),

Das bedeutet

• wenn der Automat im Zustand A ist und ein a gelesen wird, dann bleibt der Automat im Zustand A und
  
• wenn der Automat im Zustand A ist und ein c gelesen wird, dann bleibt der Automat im Zustand A.

Und (a+c) ist doch die Vereinigung also MUSS beides gleichzeitig vorkommen, oder nicht?

Gleichzeitig kann überhaupt nicht. Jedes Zeichen der Eingabe wir einzeln gelesen. Dann wird anhand des gelesenen Zeichens und des aktuellen Zustands entschieden, in welchen Zustand der Automat übergeht.