DEA/DFA der Sprache akzepiert < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Definiere einen DFA für die folgenden Sprache über dem Alphabet [mm] \{0,1\}. [/mm] Begründe, warum der DEA/DFA korrekt arbeitet.
Die Menge aller Zeichenreichen, die eine durch fünf teilbare Anzahl von Nullen und eine durch drei teilbare Anzahl von Einsen enthalten. |
Ich bin mir nicht sicher, aber es scheint, als wäre das ein sehr hässlicher und vor allem großer DEA. Ich denke da an alle Möglichleiten fünf Nullen und 3 Einsen zu verteilen.
z.B.: 11100000
11010000
11001000
.
.
.
00000111
Und dann muss noch berücksichtigt werden, dass es vielfache von fünf Nullen (0,5,10,15,...)und Vielfache von drei Einsen (0,3,6,9,...) sein sollen ....
Das ist doch schwer unschön. Oder hab ich einen "Trick" übersehen?
Vielen Dank im Voraus!
|
|
| |
|
Hallo JROppenheimer,
> Definiere einen DFA für die folgenden Sprache über dem
> Alphabet [mm]\{0,1\}.[/mm] Begründe, warum der DEA/DFA korrekt
> arbeitet.
>
> Die Menge aller Zeichenreichen, die eine durch fünf
> teilbare Anzahl von Nullen und eine durch drei teilbare
> Anzahl von Einsen enthalten.
> Ich bin mir nicht sicher, aber es scheint, als wäre das
> ein sehr hässlicher und vor allem großer DEA. Ich denke da
> an alle Möglichleiten fünf Nullen und 3 Einsen zu
> verteilen.
Eigentlich müßte sich das Ganze doch über den Schnitt zweier DEAs lösen lassen? Der erste DEA akzeptiert Wörter der ersten Sprache:
"Die Menge aller Zeichenreichen, die eine durch fünf teilbare Anzahl von Nullen enthalten."
Und der andere DEA akzeptiert Wörter der entsprechend zweiten Sprache.
Also angenommen [mm]M_1[/mm] wäre der erste Automat und [mm]M_2[/mm] der zweite Automat. Dann wäre dein gesuchter Automat: [mm]M_1\cap M_2 = \overline{\overline{M_1}}\cap\overline{\overline{M_2}}=\overline{\overline{M_1}\cup\overline{M_2}}[/mm]
Und da ein DEA ja ein Spezialfall eines NEA ist, müßte man [mm]\overline{M_1}[/mm] und [mm]\overline{M_2}[/mm], wie ![[]](/images/popup.gif) hier beispielhaft dargestellt, vereinigen können. (Wie man Automaten negiert, dürfte sich auch über Google finden lassen; Weiß es jetzt nicht mehr aus dem Kopf.)
Und dann wendest du stur die Potenzmengenkonstruktion an und erhälst damit aus diesem [mm]\texttt{NFA-}\epsilon[/mm] einen DFA, den du wiederum negieren mußt. Danach wärest du mit der Aufgabe fertig, oder aber du machst dir noch die Mühe und minimierst noch diesen DFA (ebenfalls reine Fleißarbeit. :-( ).
Ein Automat für die zweite Sprache wäre z.B umgangssprachlich ausgedrückt:
Start:
Solange 0 lese 0 ein sonst weiter1, wenn 1.
Weiter1:
Solange 0 lese 0 ein sonst weiter2, wenn 1.
Weiter2:
Solange 0 lese 0 ein sonst weiter3, wenn 1.
Weiter3:
Solange 0 lese 0 ein und bleibe in Weiter3. Gehe zu Weiter 1, wenn 1 eingelesen.
Das Wort wird akzeptiert, wenn der Automat in Weiter3 ist, wenn er das komplette Wort eingelesen hat.
Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:31 Do 19.07.2007 | | Autor: | Mumrel |
Zum Vorschlag zum Komplement:
ALso wenn man die DFAs
[mm] M_1 (\Sigma, Z_1, \delta_1, s_1, E_1) [/mm] hat und
[mm] M_2 (\Sigma, Z_2, \delta_1, s_2, E_2) [/mm]
[mm] Z_1 \cap Z_2 [/mm] = [mm] \emptyset
[/mm]
kann man doch den Durschnitt des Automaten direkt angeben ohne vorher das Komplement zu bilden:
Ich schlage vor:
[mm] M_{1,2} [/mm] = [mm] (\Sigma, Z_1 \times Z_2, \delta_{1,2}, \{s_1,s_2\}, E_1 \cap [/mm]
[mm] E_2)
[/mm]
wobei [mm] \delta_{1,2}(\{z_1,z_2\},a) [/mm] = [mm] \{\delta_1 (z1, a), \delta_2 (z2, a)\} [/mm] ist.
Oder meint ihr?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:46 So 22.07.2007 | | Autor: | RedHead |
Also da würd ich dir jetzt so zustimmen.
Da man ohne weiters die Kreuzprodukte zweier DFA`s bestimmten kann und damit genau den Schnitt dieser beiden rausbekommt ist das so schon richtig.
Wenn das deine Frage war sei sie hiermit beantwortet 
|
|
|
| |
|
Wo Du das gerade mit den DEAs schreibst, bzw. dem Schnitt.
Weiss jemand, wie ich ohne Potenzmengenkonstruktion (direkt also) einen DEA aus 2 DEAs konstruiere? gibts da einen trick? ich steh aufm Schlauch, das schlimmste ist, dass ich nciht weiss, wie ich das Problem mit den Alphabeten löse.
Sind diese disjunkt, dann isses kein problem, aber wenn die auch nur ein Symbol gleich haben, dann isses echt problematisch....
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:19 Mo 23.07.2007 | | Autor: | Mumrel |
Ich weiß nicht was du genau mit direkt meinst. Also der Potenzmengenautomat ist das intuitivste was mir dazu einfällt.
Wie würde man es denn machen wenn wir die zwei DEAs vor uns haben?
Na wir lassen die Eingabe einfach auf beide gleichzeitig vor, und akzeptieren genau dann, wenn _beide_ Automaten gleichzeitig in einem Endzustand sind.
Und [mm] \delta [/mm] macht ja auch genau das. Der Übergang d. Potenzmengen automaten wird auf die Übergänge der einzelen Automaten reduziert.
So und weil _DEA_ Automaten nun mal nur in einem Zustand (gleichzeitig) sein dürfen, bildet man alle Kombinationsmöglichekieten die es gibt (bzw. nur die erreichbaren davon).
Bei einem NEA dürften unser Konstrukt zwar in mehreren Zuständen gleichzeitig sein, aber dann sind die Endzustände das Problem, weil man die Bedinung Endzustand wenn in z1 und z2 so eben nicht formuliert.
Fazit:
Ich finde die Potenzmengenkonstrukition
- nützlich (damit geht auch die Vereinigung, wobei man das natürlich auch mit -Übergängen achen könnte)
- intuitiv, weil nahe an der Idee die den meisten wohl einfallen würde, wenn man die zwei automaten gegeben hätte.
- und sie funktioniert immer
Was genau magst du daran nicht? :)
Grüße Mumrel
|
|
|
| |
|
Haha, ich glaube hier geht was im Kontext verloren!
Merke. ICH MAG THEO ÜBERHAUPT NET....(obwohl mit der Zeit ist das sogar interessant.)
Auf jeden Fall geht es nicht darum, dass ich die Potenzmengenkonstruktion nicht mag, sondern darum, dass ich sie nach Aufgabenstellung nicht anwenden darf!
Ansonsten wäre das ja glaube ich nicht so das Problem.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:26 Do 26.07.2007 | | Autor: | Karl_Pech |
Hallo JROppenheimer,
> Haha, ich glaube hier geht was im Kontext verloren!
>
> Merke. ICH MAG THEO ÜBERHAUPT NET....(obwohl mit der Zeit
> ist das sogar interessant.)
Ich fand theo.Inf. auch besonders schwierig; Da muß man halt irgendwie durch. Dennoch müßte man ohne theo.Inf. jedesmal bis zu einem gewissen Grade kreativ sein, um DEAs für verschiedene reguläre Sprachen finden zu können. (Also mit Kreativität meine ich das, was Somebody versucht hat.)
Und bei einigen regulären Sprachen "raucht" einem dann ziemlich schnell der Kopf. :-( (Besonders während einer Klausur). Nimmt man diese ganzen "Segnungen" der theo.Inf. (wie z.B. die Potenzmengenkonstruktion) zu Hilfe, wird dieser kreative Denkvorgang etwas automatisiert.
> Auf jeden Fall geht es nicht darum, dass ich die
> Potenzmengenkonstruktion nicht mag, sondern darum, dass ich
> sie nach Aufgabenstellung nicht anwenden darf!
> Ansonsten wäre das ja glaube ich nicht so das Problem.
Wende sie trotzdem an, und minimiere danach den Automaten. Nach der Minimierung sieht man nämlich nicht mehr, wie du auf den DEA gekommen bist (durch Fleiß oder Kreativität?) Alles, was du dann noch machen mußt, ist diesen minimalen DEA zu verstehen und ihn "als eigenen Geistesblitz zu verkaufen". 
Grüße
Karl
![[user]](/images/smileys/user.gif "[user]")
|
|
|
| |
|
> Definiere einen DFA für die folgenden Sprache über dem
> Alphabet [mm]\{0,1\}.[/mm] Begründe, warum der DEA/DFA korrekt
> arbeitet.
>
> Die Menge aller Zeichenreichen, die eine durch fünf
> teilbare Anzahl von Nullen und eine durch drei teilbare
> Anzahl von Einsen enthalten.
> Ich bin mir nicht sicher, aber es scheint, als wäre das
> ein sehr hässlicher und vor allem großer DEA. Ich denke da
> an alle Möglichleiten fünf Nullen und 3 Einsen zu
> verteilen.
>
> z.B.: 11100000
> 11010000
> 11001000
> .
> .
> .
> 00000111
> Und dann muss noch berücksichtigt werden, dass es
> vielfache von fünf Nullen (0,5,10,15,...)und Vielfache von
> drei Einsen (0,3,6,9,...) sein sollen ....
>
> Das ist doch schwer unschön. Oder hab ich einen "Trick"
> übersehen?
Selbst auf die Gefahr hin, mich lächerlich zu machen, möchte ich folgenden, schön simpel regelmässigen und auch überhaupt nicht besonders hässlichen DFA vorschlagen:
[Dateianhang nicht öffentlich]
Startzustand und einziger akzeptierender Zustand ist der in der Ecke oben links.
Zum Beweis: die Zustände in derselben Zeile entsprechen gelesenen Inputs, die dieselbe Restklasse modulo 5 Nullen enthalten; die Zustände in derselben Spalte entsprechen gelesenen Inputs, die dieselbe Restklasse modulo 3 Einsen enthalten. Im akzeptierenden Zustand wird sich der Automat also genau dann befinden, wenn er sowohl 0 modulo 5 Nullen als auch 0 modulo 3 Einsen gesehen hat.
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
das sieht ziemlich cool aus...ich kuck mir das mal an, aber beim überfliegen sieht das ziemlich gut aus ....
hast Du vlt auch n tip zu meinem anderen Problem bzgl der Vereinigung zweier DEAs?!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:20 Mo 23.07.2007 | | Autor: | Somebody |
> das sieht ziemlich cool aus...ich kuck mir das mal an, aber
> beim überfliegen sieht das ziemlich gut aus ....
>
>
> hast Du vlt auch n tip zu meinem anderen Problem bzgl der
> Vereinigung zweier DEAs?!
Nein, ich habe eigentlich zur Zeit mit endlichen Automaten rein gar nichts zu tun. Es war reiner Zufall, dass ich Deine ursprüngliche Frage überhaupt gelesen habe. Aber weil ich sogleich glaubte, eine simple Lösung zu sehen, konnte ich es mir nicht verkneifen, meinen Senf dazuzugeben.
|
|
|
|
