Suche regulären Ausdruck/Grammatik für Sprache |
Mathlet
Jungspund
Dabei seit: 06.08.2016
Beiträge: 11
|
|
Suche regulären Ausdruck/Grammatik für Sprache |
|
Hallo zusammen,
mein erster Eintrag hier
Ich habe eine Aufgabe, in welcher ich zeigen möchte, dass eine Sprache regulär ist:
Alphabet ist E={0,1} und Sprache L Teilmenge von E*
L = {w | in w kommt das Teilwort 0010 höchstens einmal vor}
Ich denke, ich könnte entweder eine rechtslineare Grammatik finden oder einen regulären Ausdruck oder einen DEA... aber irgendwo hackt es gerade
- ich komm nicht dahinter, wie ich eines der drei Dinge konstruiere (wenn man eines hinbekommt, dann kommt man ja absolut easy auf die anderen...).
Über das Pumping-Lemma komm ich ja auch nicht weiter, wenn ich das Ding nicht irgendwie konstruieren kann, oder?
Danke für eure Ideen!
Liebe Grüße Matthias
EDIT: Ich lade mal die ganze Aufgabe hoch, denn die weiteren Teilaufgaben beinhalten vielleicht einen Hinweis auf die Lösung...
Mathlet hat dieses Bild (verkleinerte Version) angehängt:
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Mathlet: 06.08.2016 20:07.
|
|
06.08.2016 19:55 |
|
|
Mathlet
Jungspund
Dabei seit: 06.08.2016
Beiträge: 11
|
|
Hallo eulerscheZahl,
Erst mal Danke für deine Idee.
Den Graph hatte ich auch schon so in etwa... es müssten dann ja erst mal alle Zustände außer q8 Endzustände sein.
Aber (und vielleicht liegt hier irgendwo mein Denkfehler)...
Ich könnte mit dem DEA folgendes Wort konstruieren:
001000010 indem ich die Zustände ablaufe q0->q1->q2->q3->q4->q5->q6->q4->q4->q5
Das Wort würde (wenn q5 ein Endzustand wäre, was er zum Akzeptieren des Wortes 00100 sein müsste) akzeptiert werden, obwohl es zweimal die Folge 0010 beinhaltet... Oder hab ich da was mistverstanden?
|
|
06.08.2016 21:33 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo Ihr beiden,
Der Endzustand wird oft als Doppelkreis dargestellt.
Außerdem ist der Automat leider falsch. Das Wort 000100010 würde akzeptiert. Bin gerade am Überlegen, wie man es korrekt machen müsste.
Gruß,
Karlito
|
|
06.08.2016 21:41 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Verdammt, auch falsch... Die Transition q2 -> q1 muss reflexif sein, wie es bei euch der Fall ist.
|
|
06.08.2016 22:16 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Oh man, sorry, man sollte nicht gleichzeitig Serien gucken
Aber ich glaube das ist immernoch nicht richtig. Schau mal diese Sequenz: 001001110
Gruß,
Karlito
|
|
06.08.2016 22:37 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Ruhig bleiben und konstruktiv rangehen.
Machen wir es anders: erst NFA konstruieren und dann den DFA daraus konstruieren. Dann ergbit auch der Aufgabenteil b) Sinn.
Ich werde das jetzt mal machen, brauche dafür aber einen Moment.
Gruß,
Karlito
|
|
06.08.2016 22:56 |
|
|
|