Deterministischer Automat dessen Eingabelänge durch 3 oder 5 teilbar ist?
Als Sprache habe ich nur einen Buchstaben zur Verfügung (z.b.: x). Wenn ich jetzt eingebe "xxx" oder "xxxxx" dann soll der Automat diese Eingabe akzeptieren, weil im ersteren Fall die Länge 3 ist und im zweiteren die Länge der Eingabe 5 ist. Und da die Länge durch 3 oder 5 teilbar sein sollte, sollte diese akzeptiert werden.
Allerdings komme ich nach stundenlangen Nachdenken nicht zu der Lösung. Kann mir da jemand helfen bitte?
1 Antwort
Tipp: es reicht aus, wenn du nur den Rest betrachtest, wenn du die länge des Wortes durch eine bestimmte Zahl teilst. (Versuch zunächst die Zahl selbst zu bestimmen)
Erstelle dann für jeden möglichen Rest einen Zustand, und füge dann die entsprechenden ünergänge hinzu. Überlege dann, welche der Zustände akzeptierend sind.
Tipp:
Du hast ja im Grunde zwei Folgen von Längen, die du testen willst.
Ein mal die 3er Folge
Ein mal die 5er Folge.
Schreibe mal für beide folgen jeweils die ersten Längen, die dazu gehören. (Z.b jeweils die ersten 6)
Dir sollte dann etwas auffallen.
meinst du folgendes?
Für die 3er Folge:
q0 --> q1
q1 --> q2
q2 --> q0
Und für die 6er-Folge:
q0 --> q1
q1 --> q2
q2 --> q3
q3 --> q4
q4 --> q0
Nein, ich meine, welche längen akzeptiert werden.
Die 3er Folge lautet:
0, 3, 6, 9, 12, 15, 18, ...
Die 5er Folge lautet:
0, 5, 10, 15, 20, ...
Fällt dir was auf?
achso, also für 3:
3,6,9,12,15,18
und für 6:
5,10,15,20, ..
Auffallen tut mir das die 15 in beiden vorkommt, aber ich komme nicht drauf wie mir das bei der Umsetzung helfen soll, sorry :-/
Ich habe es nun verstanden. Ich brauche dafür 15 Zustände. Also 3*5 = 15. Und dann wiederholt sich das ganze wieder.
Welches mathematisches Konzept steckt da dahinter?
Na dann ab zum Lernen. Noch eines, ich habe auch einen nicht deterministischen Automated entworfen, allerdings nur mit 9 Zuständen.
Er ist wie gefolgt aufgebaut:
Von dem Startzustand s gehen zwei Zweige weg.
Einmal für die 3er Folge:
s --> q0
q0 --> q1
q1 --> q2
q2 --> q0
Und für die 6er-Folge:
s --> p0
q0 --> p1
p1 --> p2
p2 --> p3
p3 --> p4
p4 --> p0
Kann das stimmen?
Ich glaube du meinst beim 2. Dass es von p_0 zu p_1 gehen soll oder?
Also ja, wenn du es als NDA modellieren willst, kannst du einfach zwei Zyklen bilden lassen, wobei einer die Länge 3 und der andere dir Länge 5 hat. Wichtig ist halt nur, dass du die richtigen akzeptierenden zustände wählst.
ups, ja natürlich damit sollte p0 zu p1 gemeint sein, sorry.
Genau meine Endzutände wären q2 und p4.
Danke richte ich mal ein riesen Dank aus und wünsche dir alles Gute! Danke, danke danke! :-)
Der Gedankengang ist mir bekannt. Somit hätte ich folgende Zustände:
q0, q1, q2, q3, q4 und q5 --> Jeweils für den Rest.
q3 und q5 wären meine Endzustände, da Rest 0 (teilbar)
Dann kann ich folgende Übergänge eintragen:
Habe ich beispiels 6 "x" also "xxxxxx" so ende ich hiermit in Zustand q0. Also muss dieser auch ein akzeptierender sein.
Habe ich 10 "x", also "xxxxxxxxxx" so ende ich auf q4.
Mit 11 "x" ende ich auf q5, was aber ein akzeptierender Zustand ist was wiederrum nicht möglich ist.
Egal wie ich es drehe, ich komme immer wieder auf derartige Probleme. Warum denke ich hier so falsch :-S