Aufgabenblatt 5

Theorie Aufgaben

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Aufgabenblatt 5
Die Grammatik mal wieder…^^

Kann mir mal einer ein Beispiel geben wie ich sowas machen muss? Hab mir das Script nun ne stunde durchgeschaut. kam immer wieder zu der seit wo N,T,P,S erklärt wurde. sowas steht nun auch auf dem Übungsblatt.

Da steht dann noch N=…, T=…, P=…

wie geh ich da nun vor? Was will man da von mir?


Ich verstehe die Frage nicht ganz …

N sind die sogenannten Nicht-Terminale (große Buchstaben), also Zeichen, die noch ersetzt werden müssen und zwar nach den Regeln von
P, welche einfach sagen, wenn ich ein A habe, dann kann ich daraus ein a machen (A, a), denn a (kleine Buchstaben) gehört zu
T, den Terminalen.
Wenn eine Reihe nur aus Terminalen, also “kleinen Buchstaben” besteht, dann ist es ein Wort.
Wenn ein Wort durch die Grammatik gebildet werden kann, dann ist es ein Wort der Grammatik.
Ach ja: S ist das Start-Zeichen (aus der Gruppe der Nicht-Terminale).

Das dürfte es doch ca. sein, oder?


Meint ihr wir sollen das bei der 5.1 a) folgendermaßen schreiben?:

a[sup]n[/sup]*c[sup]m[/sup]b[sup]3n[/sup]


ich hab keine ahnung… :cry:


Kaum zu glauben, aber ich habe die komplette 5.1 fertig …
Ich glaube so früh war ich noch nie dran (Durchschnitt ca. ½ Tag vor Abgabeschuss)


erklär mir doch ma was du dann gemacht hast^^


ist damit
P = {(S, aSb3), (S, cA), (A, cA), (A, c)}

das
S → aSb3
S → cA
A → cA
A →c

gemeint?

oder versteh ich das wirklich falsch?^^ :listen:


Ja.
Beispiel

L(H) = {a[sup]n[/sup]b[sup]n[/sup] | n ≥ 1}
G = (N, T, P, S)
T = {a, b}* (bedeutet mit ε)
N = {S}
P = {(S, aSb), (S, ab)}

ab muss ja mindestens einmal vorkommen (n ≥ 1), deswegen ist der Terminal-Fall (S, ab).

Bsp:

S ⇒ aSb ⇒ aSb ⇒ aaSbb ⇒ aaSbb ⇒ aaabbb


ok somit sind alle hindernisse überwunden für mich. dann kann ich ja ins WE gehn :smiley:


Hi!
Ich hatte leider die Forlesung zur Grammatik verpasst :rolleyes: und haette da mal noch ein paar Fragen:

Darf eigentlich eine Grammatik einer Sprache komplett nur Umformungen von S→Terminale enthalten oder müssen auch Nichtterminale vorhanden sein?

Wird bei einer Sprachdefinition ein Wertebereich > 0 angegeben, heisst das dann, dass das Startsymbol nicht S sondern beispielsweise aSb für L = {a^nb^n | n > 0} ist?

Hm, irgendwas anderes war mir auch noch nicht so klar, komm aber grade nichtmehr drauf…

Danke schonmal
Gruß

Nic

???
Ist die Lösung bei 5.1 a)
S→acccb3
oder verstehe ich die Aufgabe ganz falsch???

Gruß


So wie ich das verstanden hab musst du eine Sprachdefinition à la:
L(G) = {a^x b^y c^z | x,y,z ∈ K}
angeben, oder nicht?


Keine Ahnung!! Ich muß da eine Sprachdefinition angeben oder was???
Verstehe ich nicht so ganz!


Vielleicht bin ich ja zu blöd um das zu verstehen!

Aufgabe 5.1
Ich denke eher so; aber OHNE Gewaehr!



a)
L(G) = {a^nc^mb^3 | n>=1, m >=2}
Es gibt durch die Produktionen genau 3b, minimal 1a und minimal 2c.

b)
acb^3 ist nicht moeglich, das kleinste Wort ac^2b^3 ist.
Entstehung:
aSb^3 -> acAb^3 -> accb^3 = ac^2b^3

a^2c^4b^6 ist moeglich:
aSb^3 -> aaSb^3b^3 -> a^2cAb^6 -> a^2ccAb^6 -> a^2cccAb^6 -> a^2ccccb^6 = a^2c^4b^6

a^3b^2c^12 ist nicht moeglich, da das kleinste Auftreten von b 3 ist.
Dies ergibt sich aus der Startproduktion.
Ausserdem gibt es keine Produktionen, so dass c nach b auftreten kann.

Du hast bei b^3 noch das n vergessen, es müsste doch heißen …b^3n, da ja immer 3mal soviel b erzeugt werden wie a. Sonst hab ich’s genauso…

Flo


UND n >= 0!


Und b^a wobei a vielfache von 3 und a >= 3


Also so?

vgl. Anhang

Attachment:
sprache.jpg: https://fsi.cs.fau.de/unb-attachments/post_29112/sprache.jpg