Informatiker Board | formale Sprachen | Suche regulären Ausdruck/Grammatik für Sprache

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Suche regulären Ausdruck/Grammatik für Sprache

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Seiten (2): [1] 2 nächste »

Suche regulären Ausdruck/Grammatik für Sprache

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Mathlet
Jungspund

Dabei seit: 06.08.2016
Beiträge: 11

Suche regulären Ausdruck/Grammatik für Sprache

Zitatantwort auf diesen Beitrag erstellen

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

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

Nehmen Sie Mathlet in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

eulerscheZahl hat dieses Bild (verkleinerte Version) angehängt:

__________________
Syntax Highlighting fürs Board (Link)

06.08.2016 21:03

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

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 Karlito ist männlich

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

Nehmen Sie Karlito in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

eulerscheZahl hat dieses Bild (verkleinerte Version) angehängt:

__________________
Syntax Highlighting fürs Board (Link)

06.08.2016 21:59

Mathlet
Jungspund

Dabei seit: 06.08.2016
Beiträge: 11

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! :-)

Mathlet hat dieses Bild (verkleinerte Version) angehängt:

06.08.2016 22:10

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

Karlito hat dieses Bild (verkleinerte Version) angehängt:

06.08.2016 22:12

Mathlet
Jungspund

Dabei seit: 06.08.2016
Beiträge: 11

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!

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Mathlet: 06.08.2016 22:16.

06.08.2016 22:15

Karlito Karlito ist männlich

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 Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

Karlito hat dieses Bild (verkleinerte Version) angehängt:

06.08.2016 22:18

Mathlet
Jungspund

Dabei seit: 06.08.2016
Beiträge: 11

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

Mathlet hat dieses Bild (verkleinerte Version) angehängt:

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Mathlet: 06.08.2016 22:34.

06.08.2016 22:23

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

06.08.2016 22:37

Mathlet
Jungspund

Dabei seit: 06.08.2016
Beiträge: 11

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

Mathlet hat dieses Bild (verkleinerte Version) angehängt:

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Mathlet: 06.08.2016 22:48.

06.08.2016 22:46

Mathlet
Jungspund

Dabei seit: 06.08.2016
Beiträge: 11

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

Mathlet hat dieses Bild (verkleinerte Version) angehängt:

06.08.2016 22:54

Karlito Karlito ist männlich

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

Seiten (2): [1] 2 nächste »

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Suche regulären Ausdruck/Grammatik für Sprache