Aufgabenblatt 5


@thomas_: jep, genau so!


S an sich ist ja schon ein Nicht-Terminal-Zeichen, das brauchst du auf jeden Fall, aber sonst gibt’s da eigentlich keine Einschränkungen.
Wird halt eine sehr langweilige Sprache (z.B. L={a} => P={(S,a)} ), oder eine sehr große Grammatik (für die meisten Sachen unendlich groß…)

A ja, und die Lösung von thomas_ für die a) sollte stimmen.


Vielleicht habe ich was falsch verstanden, aber muss a und b nicht mindestens 1 mal vorkommen (m größer gleich 0 wäre also falsch, es muss m größer 0 sein)?
Meine Lösung seht ihr im Anhang.
Jetzt geh ich mir mal weiter die Zähne an der c) ausbeißen :wink:

MfG

Attachment:
lsg.png: https://fsi.cs.fau.de/unb-attachments/post_29127/lsg.png


Ne, a und b können auch nie vorkommen, du kannst doch z.b. nur folgende Produktionen verwenden:
(S, cA), (A, cA), (A, cA), (A, c)
was dann zu c^4 führen würde


Ah ja, ist klar, ich hab verpeilt dass aus S auch gleich cA werden kann.
Danke.


Aufgabe 5.1c) 1

Anhang aktualisiert, hatte zuvor b und c vertauscht

Irgendjemand Einwände?

Attachment:
5_1_c_1.jpg: https://fsi.cs.fau.de/unb-attachments/post_29138/5_1_c_1.jpg


a^m b^n c^n c^m

außen anfangen:
(S, aSc)
=> m muss mindestens einmal vorkommen
(S, aAc)
(also muss beim wechsel das Ganze mindestens einmal geschrieben werden)
(A, bAc)
(A, ε)


@thomas_: Keine Einwände :wink:


@Nico darf ich nicht nur aus dem Startsymbol das leere Wort erzeugen?
Welches Wort aus der Sprache kann ich damit nicht erzeugen?


Thomas, (S, aAc) lässt sich auch in Form (S, A) schreiben, das “spart” 2 Symbole :wink:


Wenn ich eine Produktion (S, A) habe anstatt (S, aAc) kann ich doch aber z.b. auch nur “bc” erzeugen… was nicht sein darf, da “a” ja mindestens einmal vorkommen muss…?


@TheChip.
Hast Recht.

Häng des Bild nochmal an, dass man net immer blättern muss.

Attachment:
5_1_c_1.jpg: https://fsi.cs.fau.de/unb-attachments/post_29151/5_1_c_1.jpg


Nein, weil S Startsymbol ist, wird nach (S, aSc) oder (S, ac) oder (S, aAc) ‚a‘ mindestens einmal erzeugt!

damn
Diese Grammatik verdreht einem aber heftigst den Kopf!


Stimmt! :slight_smile:


Nicht, wenn du auch ZUSÄTZLICH noch (S, A) hast.
Dann kannst du ja mit dieser Produktion starten (sie enthält das Startsymbol S) und wirst nie ein „a“ bekommen.

Reden wir jetzt grad aneinander vorbei?! :wink:

Also so wies Thomas da oben hat stimmts, und kürzer sollte es auch nicht gehen?


OK, ich habe einen Fehler!!! :wand:


Ich weiß nach wie vor nicht, warum an nur aus dem Startsymbol ε erzeugen kann.

Demnach ist meine gezeigte Lösung mit 4 Regeln kürzer.


btw. hat schon einer von euch die dritte aufgabe von 5.1c gepackt?
ich versteh die net so ganz :confused:
die anderen sind null problemo…


Da bin ich mir auch noch nicht so sicher…
Ich hatte jetzt hier was gefunden (Folie 4/51) und demnach würde ich das jetzt so interpretieren, dass {a,b}* die “Menge aller Ketten ueber A” ist - d.h. die einzigen zwei Worte der Sprache waeren “a” und “b”. Das steht aber im Widerspruch zu der Bedingung |w| = 2k; k ≥ 1.
Insofern kanns eigentlich doch nur so sein, dass {a,b} die Menge der Nichtterminalen sind, und {a,b}* alle Kombinationen dieser Nichtterminalen zulaesst.
Und damit waere die einzige Bedingung dass das Wort eine gerade Anzahl von Nichtterminalen enthaelt…
Vielleicht dann sowas wie:
S → a²S
S → b²S
S → a²
S → b²
S → ab
S → ba

[edit]
Damit alle Kombinationen moeglich sind muessten wahrscheinlich auch noch
S → abS
S → baS
mit rein faellt mir grade ein…

Da ich aber grade erst aufgestanden bin uebernehm ich noch fuer nix ne Haftung :open_mouth: