Minimal-DFA < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:19 Sa 15.11.2008 | | Autor: | Manyak |
Hallo, Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich soll folgende Aufgabe lösen: Sei [mm] \sum [/mm] = {a,b}.
Geben Sie einen Minimal-DFA M für die Sprache der Wörter über [mm] \sum [/mm] an, die bbb nicht als Teilwort enthalten. Beweisen Sie die Korrektheit und die Minimalität von M.
Muss der Automat nun auch das leere Wort akzeptieren?
und wie kriege ich heraus, ob mein Automat minimal ist?
Danke, hoffe ihr könnt mir weiterhelfen
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:26 Sa 15.11.2008 | | Autor: | Gilga |
Leeres Wort muss er auch erkennen
Lies dir http://de.wikipedia.org/wiki/Deterministischer_endlicher_Automat
durch
Oder überlege wieviele Zustände für dein Automat relevant sind.
(Anzahl der aufeinanderfolgenden b)
Folglich 4 Zustände
Beweis durch geschwafel über zustände (einen akzeptierenden automaten angeben und erzählen warum es nicht weniger sein können --- unprofessionelles Verhalten:) oder wikipedia artikel (richtiger beweis)
|
|
|
|
