Hey ich habe in meinem informatik studium einpaar aufgaben zu deterministischen Automaten die ich nicht wirklich lösen kann, kann mir da jemand helfen?
Aufgabe 1:
Gegeben sei die Sprache L mit:
L= {w | w = xabc mit x∈Σ} mit Σ = {a,b,c}
Geben sie einen deterministischen endlichen Automaten für die Sprache an.
Aufgabe 2:
Gegeben sei folgende Grammatik:
P = {S → bbT
T → U
U → ε | aS}
Wandeln Sie die gegebene Grammatik in eine äquivalente Typ-3-Grammatik
um.
Aufgabe 3:
Es sollen zwei verschiedene deterministische endliche Automaten entwickelt
werden:
a) Automat A1 der alle Binärstrings akzeptiert, die als Dualzahl interpretiert
durch 2 teilbar sind. D.h. der Automat erkennt folgende Sprachen:
L1 = {w mod 2 = 0 | mit Σ{0,1}+}
b)
Automat A2 der alle Binärstrings akzeptiert, die als Dualzahl interpretiert
durch 4 teilbar sind. D.h. der Automat erkennt folgende Sprachen:
L1 = {w mod 4 = 0 | mit Σ{0,1}+}
Wäre wirklich schön wenn irgendeiner mir die lösungen erklären könnte bin am verzweifeln
2 Antworten
1 und 2 sind mir grad ein wenig zu viel arbeit solltest du aber hinbekommen. Oder geb an was genau du nicht kannst und ich schau mal ob mir was einfällt.
3 a) ist bei einem binärwert die erste stelle 1, ist die zahl ungerade.
b) sind die ersten beiden stellen 1 ist mod 4<0
Hast du generell probleme mit automaten und formalen sprachen?
Dann mach das mal. Ich hab das grad in informatik lk durchgenommen also keine panik
Deas sind ja noch einfach. Etwas weiter oben in der chomsky hierachie wirds kompliziert
Sorry, aber wo genau hast du denn da Probleme? Bin grad unterwegs, deshalb nur so viel.
- Ist nichts weiter als ein Automat, der Wörter in Form {a,b,c}abc. Du hast also einen Anfangszustand q0. In den Zustand q1 kommst du durch welche folgenden Buchstaben? Dann malst du da einfach die Übergänge hin. Fertig. Hier ist ein Beispiel https://de.wikipedia.org/wiki/Deterministischer_endlicher_Automat
- Kurze def Typ 3 Grammatiken: "Typ-3-Grammatiken werden auch reguläre Grammatiken genannt. Es handelt sich um Typ-2-Grammatiken, bei denen auf der rechten Seite von Produktionen genau ein Terminalsymbol auftreten darf und maximal ein weiteres Nichtterminalsymbol" Das ist nur ein bisschen umformen, bis zur Definition und
- Wieder Automat malen. Wann ist eine Binärzahl durch 2 und wann durch 4 teilbar? Kann man sich auch bei Wikipedia raussuchen... ;)
Falls ich zu Hause bin und das nochmal sehe, kann ich auch gerne Lösungen dazu schreiben oder vielleicht erbarmt sich da auch jemand anderer, aber die Sachen sind im Prinzip so einfach, dass ich nicht glaube, dass du dich auch nur im entferntesten damit auseinandergesetzt hast. :/
Ja wir haben automaten erst seit kurzem und ich war leider krank als wir das durchgenommen haben und hatte noch keine Zeit es wirklich effektiv nachzuhaolen