CFG Computerlinguistik?

G = ⟨{S}, {a, b, c, d}, {S → aSc | bSd | ε}, S⟩

Welche Sprache werde von dieser Grammatik generiert?

Ich verstehe welche Sprache damit erzeugt wird, da sie auch recht simpel ist, jedoch weiß ich nicht wie ich das aufschreiben soll. Kann mir Jemand weiterhelfen?

Answer 1

[malte314]

Es handelt sich um eine klassische Klammer- oder Dycksprache (https://de.wikipedia.org/wiki/Dyck-Sprache) mit den Klammerpaaren a, c und b, d. Folglich sind in der Sprache alle wohlgeformten Klammerausdrücke.

Korrektion: Es ist die beschriebe Dycksprache geschnitten mit der regulären Sprache (a+b)*(c+d)*

Woher ich das weiß: Studium / Ausbildung – B.Sc. Computer Science

Answer 2

[Seliba]

Edit: Meine vorherige Antwort war leider vollkommen falsch, ich hatte mich verlesen

Die Sprache sollte folgende sein:

$L\ =\ \left\{w\in\left\{a,b,c,d\right\}^{\ast}\left|count\left(w,\ a\right)=count\left(w,\ c\right)\ und\ count\left(w,\ b\right)\ =\ count\left(w,\ d\right)\right|\right\}$

Einfach immer genauso viele a's wie c's und b's wie d's. ε ist mit x = y = 0 enthalten. Ist ohne Definition einer Funktion zum Zählen der Zeichen in einem Wort leider ziemlich informell. Eine wirklich schönere Möglichkeit gibt es meines Wissens nicht.

Woher ich das weiß: Studium / Ausbildung – Informatikstudent

Comments

[malte314]

Die Antwort ist nicht präzise, denn nach deiner Beschreibung wäre das Wort »abad« in der Sprache, was es allerdings nicht ist. Zum Zählen der Vorkommnisse eines Symbols a in einem Wort w ist übrigens die Schreibweise |w|_a geläufig (das _a soll dabei freilich im Index stehen).

[Seliba]

@malte314

Du hast natürlich vollkommen recht, die Antwort ist immer noch vollkommen falsch. Ich weiß nicht, wie ich darauf gekommen bin. Könnte ich meine Antwort löschen, hätte ich es schon getan…