Automat als rekursives System < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:35 So 13.04.2008 | | Autor: | bob86a |
| Aufgabe | Wir betrachten den auf der Folgeseite abgebildeten endlichen Automaten mit den Zuständen A, B, C, D, wobei A sowohl der Anfangs- als auch der Endzustand ist. Ein nichtleerer String s = [mm] s_{1}...s_{n} [/mm] von Symbolen [mm] s_{1}, [/mm] ..., [mm] s_{n} \in [/mm] { 0, 1} heißt vom endlichen Automaten
akzeptiert, wenn wir in dem Graphen des Automaten einem Pfad der Länge n folgen können, der im Punkt A startet und dort auch wieder endet und die n Kanten, die mit den Symbolen [mm] s_{1}, [/mm] ..., [mm] s_{n} [/mm] indiziert sind, in der vorgeschriebenen Richtung und Reihenfolge durchläuft. Die von dem endlichen Automaten akzeptierte Sprache besteht gerade aus allen vom Automaten akzeptierten Strings, wobei wir der Einfachheit halber das leere
Wort ausschließen.
Konstruiere ein rekursives System, daß die vom Automaten akzeptierte Sprache repräsentiert!
Der Automat: ![[a]](/images/paperclip.gif "Dateianhänge") [Bild Nr. None (fehlt/gelöscht)] |
Hallo!
Ich habe ein echtes Problem mit dieser Aufgabe... Leider habe ich keine Ahnung, wie ich das angehen soll... Irgendwie muss ich ja Axiome basteln, so dass ich eine Sprache erhalte. Aber wo kann ich da ansetzen? Ich habe keine Ahnung wie ich anfagen soll.
Im Endeffekt sind ja sicher nur 1 und 0 akzeptierte Wörter, sprich aus die müsste ich den String im Prinzip "Herunterbrechen"...
Als zwei Grundlegende Axiome könnte ich mir also schon mal Wort 1 und Wort 0 oder etwas in der Art vorstellen.
Für ein klein wenig Hilfe wäre ich dankbar :)
Gruß, Bernd
Dateianhänge:
Anhang Nr. 1 (Typ: GIF) [nicht öffentlich]
|
|
| |
|
Hallo bob86a!
> Im Endeffekt sind ja sicher nur 1 und 0 akzeptierte
> Wörter, sprich aus die müsste ich den String im Prinzip
> "Herunterbrechen"...
> Als zwei Grundlegende Axiome könnte ich mir also schon mal
> Wort 1 und Wort 0 oder etwas in der Art vorstellen.
> Für ein klein wenig Hilfe wäre ich dankbar :)
Na, aber nach nur 1 oder nur 0 bist du doch nicht im Endzustand!? Ich würde anfangen mit 1010, und dann erstmal schauen, wenn ich die erste 1 gegangen bin, kann ich, bevor ich die 0 gehe, auch nochmal beliebig oft (11) laufen, also hätten wir schon mal 1(11)*0. Hier dann das Gleiche mit der 0: 1(11)*0(00)*1 usw.. Allerdings kannst du erstens natürlich auch komplett anders herum laufen, oder nach der ersten 1 auch einfach mit einer 1 zurück zu A und vor dort dann wieder entweder stop oder im Uhrzeigersinn oder gegen den Uhrzeigersinn. Also man muss da wohl ziemlich viele Sachen betrachen.
Was genau bedeutet denn "rekursives System"?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Mi 16.04.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
