Wie würde ein (N)DEA für folgende Sprache aussehen?

Question

Frage:

Wie würde ein (N)DEA für folgende Sprache aussehen?

L = {wcv | w,v ∈ {a,b}* ∧ |w| > |v|}

Wie gewährleiste ich |w| > |v| ?

Ich dachte an den Startzustand S0, mit einem Pfeil zu S1, wenn ein c gelesen wird.

Und dann könnte ich einen Pfeil von S0 auf S0 mit a,b, und das selbe mit S1 auf S1. Aber damit gewährleiste ich noch nicht, dass |w| > |v|.

Auch wenn ich erzwingen würde, dass vor dem c mindestens einmal ein a oder b gelesen wird, bringt das ja nichts, da in S1 wieder beliebig viele, also mehr a's und b's als bei S0 gelesen werden können.

Liebe Grüße

Answer 1

Die Sprache ist nicht regulär. Es gibt deshalb keinen NDEA, der sie akzeptiert.

Comments

Stimmt, dankeschön.

Wenn eine Sprache angegeben wäre, zu der man einen regulären Ausdruck finden soll, dann wäre das ja eine Möglichkeit, zuerst einen (N)DEA zu zeichnen, um davon zum regulären Ausdruck zu kommen, oder?

Gibt es irgendeine Herangehensweise, um eine kontextfreie Grammatik für die Sprache zu finden, ohne, direkt aus dem Kopf, also auch mit einem Umweg, welcher mir den Weg zu einer Lösung erleichtert?

Liebe Grüße

---

Wenn eine Sprache angegeben wäre, zu der man einen regulären Ausdruck finden soll, dann wäre das ja eine Möglichkeit, zuerst einen (N)DEA zu zeichnen, um davon zum regulären Ausdruck zu kommen, oder?

Ja.

Gibt es irgendeine Herangehensweise, um eine kontextfreie Grammatik für die Sprache zu finden, ohne, direkt aus dem Kopf, also auch mit einem Umweg, welcher mir den Weg zu einer Lösung erleichtert?

Der erste Schritt wäre, herauszufinden mittels welcher Logik man L wie beschreiben kann. Schon da muss man den Kopf einschalten. Ich sehe deshalb keinen Sinn darin, einen Umweg in der Hoffnung zu gehen, auf vorgefertigte Algorithmen zu stoßen.

---

Das nicht. Aber Tricks gibt es ja immer. Ich finde es ziemlich schwer, kontextfreie Grammatiken zu finden, sodass wirklich nur die Wörter, die erlaubt sind, produziert werden können.

---

Vielleicht gibt es ja ein paar Logiken, die häufiger vorkommen bzw. verwendbar sind.

Ist bei Mathematik ja auch so :)