Informatiker Board | Druckvorschau: Suche regulären Ausdruck/Grammatik für Sprache

Geschrieben von Mathlet am 06.08.2016 um 19:55:

Suche regulären Ausdruck/Grammatik für Sprache

Hallo zusammen,

mein erster Eintrag hier Willkommen

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 Zunge raus

- 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...

Geschrieben von eulerscheZahl am 06.08.2016 um 21:03:

In q8 wurde die Zeichenfolge 0010 zweimal gefunden, also ist das der einzige nicht akzeptierende Endzustand (ich weiß gerade nicht auswendig, wie ich die anderen als Endzustand markieren kann).

Geschrieben von Mathlet am 06.08.2016 um 21:33:

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?

Geschrieben von Karlito am 06.08.2016 um 21:41:

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

Geschrieben von eulerscheZahl am 06.08.2016 um 21:59:

Ich war nur zu faul, zu suchen, wie ich den Doppelkreis in GraphViz hinkriege.

Ich versuche es nochmal, hoffentlich habe ich nichts übersehen.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

digraph {
	node [shape = doublecircle]
	q0 -> q1 [label="0"]
	q0 -> q0 [label="1"]
	q1 -> q2 [label="0"]
	q1 -> q0 [label="1"]
	q2 -> q3 [label="1"]
	q2 -> q2 [label="0"]
	q3 -> q3 [label="1"]
	q3 -> q4 [label="0"]
	
	q4 -> q5 [label="0"]
	q4 -> q4 [label="1"]
	q5 -> q6 [label="0"]
	q5 -> q4 [label="1"]
	q6 -> q7 [label="1"]
	q6 -> q6 [label="0"]
	q7 -> q4 [label="1"]
	node [shape = circle]
	q7 -> q8 [label="0"]
	
	q8 -> q8 [label="0/1"]
	
	rank = same {q0 q1 q2 q3 q4 q5 q6 q7 q8}
}

Geschrieben von Mathlet am 06.08.2016 um 22:10:

Ah! Das schaut gut aus!
Ich bin gerade auf fast den gleichen gekommen, aber ich hatte q7 anders definiert - habs jetzt an deinen Graph angepasst und sehe gerade keinen Fehler mehr! Danke! :-)

Geschrieben von Karlito am 06.08.2016 um 22:12:

Leider immernoch falsch, da 001110 das erste Wort 0010 verbrauchen würde. Beim zweiten Teil passt es, wenn ich nichts übersehen habe.

Hier meine Lösung:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:

digraph 0010 {
	rankdir=LR

	node  [shape=none] qs [label=""]
	node  [shape=circle] q8
	node [shape=doublecircle]
  qs -> q0
	q0 -> q0 [label=1]
	q0 -> q1 [label=0]
	q1 -> q2 [label=0]
	q2 -> q1 [label=0]
	q1 -> q0 [label=1]
	q2 -> q3 [label=1]
	q3 -> q0 [label=1]
	q3 -> q4 [label=0]
	q4 -> q4 [label=1]
	q4 -> q5 [label=0]
	q5 -> q6 [label=0]
	q6 -> q7 [label=1]
	q7 -> q8 [label=0]
	q8 -> q8 [label="0,1"]

	q5 -> q4 [label=1]
	q6 -> q5 [label=0]
	q7 -> q4 [label=1]
}

Gruß,

Karlito

Geschrieben von Mathlet am 06.08.2016 um 22:15:

Nein! Halt - immer noch ein Fehler! weil ja 0010010 akzeptiert wird... Zunge raus

EDIT: Da war ich zu spät, aber Karlitos Lösung ist auch noch nicht richtig... Wir sind nah dran!

Geschrieben von Karlito am 06.08.2016 um 22:16:

Verdammt, auch falsch... Die Transition q2 -> q1 muss reflexif sein, wie es bei euch der Fall ist.

Geschrieben von Karlito am 06.08.2016 um 22:18:

Das sollte es jetzt aber sein:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

digraph 0010 {
	rankdir=LR

	node  [shape=none] qs [label=""]
	node  [shape=circle] q8
	node [shape=doublecircle]
  qs -> q0
	q0 -> q0 [label=1]
	q0 -> q1 [label=0]
	q1 -> q2 [label=0]
	q2 -> q2 [label=0]
	q1 -> q0 [label=1]
	q2 -> q3 [label=1]
	q3 -> q0 [label=1]
	q3 -> q4 [label=0]
	q4 -> q4 [label=1]
	q4 -> q5 [label=0]
	q5 -> q6 [label=0]
	q6 -> q7 [label=1]
	q7 -> q8 [label=0]
	q8 -> q8 [label="0,1"]

	q5 -> q4 [label=1]
	q6 -> q6 [label=0]
	q7 -> q4 [label=1]

}

Einspruch?

Gruß,

Karlito

Geschrieben von Mathlet am 06.08.2016 um 22:23:

Das wäre mein aktueller Versuch.. spontan finde ich auch keine Fehler mehr... (ja, Startzugang vergessen!)

EDIT: Bei Karlito würde folgendes Wort akzeptiert werden:
0010010
->q0->q1->q2->q3->q4->q5->q4->q5

EDIT2:
Sollte meine Lösung korrekt sein, dann verstehe ich nicht mehr die Teilaufgabe b) (=>Siehe Anhang erster Post), weil ich keinen neuen Zustand mehr brauche, um einen DEA zu konstruieren (mit b) und 7 Zuständen habe ich a) ja bereits bewiesen und einen DEA konstruiert....)...

Geschrieben von Karlito am 06.08.2016 um 22:37:

Oh man, sorry, man sollte nicht gleichzeitig Serien gucken großes Grinsen

Aber ich glaube das ist immernoch nicht richtig. Schau mal diese Sequenz: 001001110

Gruß,

Karlito

Geschrieben von Mathlet am 06.08.2016 um 22:46:

Nächster Versuch... Oh mann... sowas im Examen und traurig

Und wenn ich gerade drüber nachdenke, passt es wieder nicht...
00110010 wird nicht akzeptiert....

Geschrieben von Mathlet am 06.08.2016 um 22:54:

Doch noch mal einen neuen Zustand dazu... Gibt es jetzt noch Einsprüche?

Geschrieben von Karlito am 06.08.2016 um 22:56:

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