Forum
 
Fragen
 
Suchen
 
Über Uns
 
 

Suche regulären Ausdruck/Grammatik für Sprache
Neue Frage »

06.08.2016, 19:55 Auf diesen Beitrag antworten »
Mathlet 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...
 
 
06.08.2016, 21:03 Auf diesen Beitrag antworten »
eulerscheZahl

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).
06.08.2016, 21:33 Auf diesen Beitrag antworten »
Mathlet

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:41 Auf diesen Beitrag antworten »
Karlito

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
 Anzeige
 
06.08.2016, 21:59 Auf diesen Beitrag antworten »
eulerscheZahl

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}
}
06.08.2016, 22:10 Auf diesen Beitrag antworten »
Mathlet

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! :-)
06.08.2016, 22:12 Auf diesen Beitrag antworten »
Karlito

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
06.08.2016, 22:15 Auf diesen Beitrag antworten »
Mathlet

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!
06.08.2016, 22:16 Auf diesen Beitrag antworten »
Karlito

Verdammt, auch falsch... Die Transition q2 -> q1 muss reflexif sein, wie es bei euch der Fall ist.
06.08.2016, 22:18 Auf diesen Beitrag antworten »
Karlito

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
06.08.2016, 22:23 Auf diesen Beitrag antworten »
Mathlet

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....)...
06.08.2016, 22:37 Auf diesen Beitrag antworten »
Karlito

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:46 Auf diesen Beitrag antworten »
Mathlet

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....
06.08.2016, 22:54 Auf diesen Beitrag antworten »
Mathlet

Doch noch mal einen neuen Zustand dazu... Gibt es jetzt noch Einsprüche?
06.08.2016, 22:56 Auf diesen Beitrag antworten »
Karlito

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, 23:00 Auf diesen Beitrag antworten »
Karlito

Ja, Einspruch: 0010 011010 wird nicht akzeptiert.
06.08.2016, 23:16 Auf diesen Beitrag antworten »
Mathlet

Stattgegeben Daumen hoch
Wie ich da nen schönen NEA konstruiere unglücklich
Ich hab bisher eigentlich nur DEAs konstruiert und nen gegebenen NEA mit dem Potenzmengenalgorithmus auf nen DEA reduziert. Ist das konstruieren eines NEAs einfacher? Dann wäre es sicherlich die bessere Herangehensweise.
NEA --- Potenzmengenalgorithmus ---> DEA --- Table-Filling-Algorithmus ---> min. DEA
06.08.2016, 23:39 Auf diesen Beitrag antworten »
Karlito

Ja, der NEA ist einfacher.

Ich habe einen (Irrtum nicht ausgeschlossen) aber ich glaube es gibt einen einfacheren. Die Potenzmengenkonstruktion wird so recht groß.

Die finalzustände sind absichtlich erstmal "falschherum" gewählt. Durch Komplementbildung erhalten wir am Ende den DEA für die Aufgabenstellung. Komplement darf erst nach der Konstruktion des DEA gebildet werden.

Gruß,

Karlito
07.08.2016, 00:34 Auf diesen Beitrag antworten »
Karlito

Wird heute erstmal nix. Bin zu unkonzentriert und müde.

Ich setze mich morgen noch einmal an das Problem.

Gruß,

Karlito
07.08.2016, 09:35 Auf diesen Beitrag antworten »
Mathlet

Kein Ding! Vielen Dank schon mal für deine Hilfe und auch die von eulerscheZahl!
Ihr habt mich zu einer vermutlich richtigen Lösung geführt Daumen hoch
Hab gestern auch mal den regulären Ausdruck gemacht... großes Grinsen
Die Grammatik hab ich mir erst mal gespart...
07.08.2016, 09:42 Auf diesen Beitrag antworten »
Karlito

Gut, dann setze ich mich da nicht noch einmal ran?

Gruß,

Karlito
07.08.2016, 12:26 Auf diesen Beitrag antworten »
Mathlet

Ich glaube, mein Graph müsste jetzt endgültig passen. Also danke, du musst dir nicht noch einmal extra die Mühe machen!
Nur noch kurz die Frage: Ich hab das richtig verstanden, dass ich mit diesem Graph eines DEA ja auch schon bewiesen habe, dass die Sprache definitiv regulär ist, richtig?
07.08.2016, 12:47 Auf diesen Beitrag antworten »
Karlito

Naja, schon wenn du einen NFA angeben kannst, ist die Sprache regulär. Hier wäre die Argumentationskette so, dass man einen NFA für die Komplement-Sprache angeben kann. Da NFA regulär sind und reguläre Sprachen unter Komplement abgeschlossen sind, ist die Sprache regulär.

Gruß,

Karlito
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


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

 
© 2005-2019 bei Informatikerboard.de | Archiv, alt, neueste | Kontakt | Jugendschutz | Nutzungsbedingungen