Endlicher Automat < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:18 So 01.06.2008 | | Autor: | Parkan |
| Aufgabe | Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Sei Sigma = [mm] ({x_{1},x_{2},...,x_{n}})
[/mm]
fuer n [mm] \ge [/mm] 1 ein endlicher Alphabet. Definieren Sie einen deterministischen, endlichen Automaten, der die Menge [mm] L:={x_{i}x_{i}|1\le i \le n}* [/mm]
akzeptiert.
Geben Sie Ihre Konstruktionsidee an und beschreiben Sie zu jedem Zustand s, was gilt,
wenn sich der Automat in s befindet.
Hinweis: Zeichnen Sie dazu KEIN Zustands(überführungs)diagramm! |
Hallo
Bei dieser aufgabe, fehlt mir warscheinlich das Basiswissen. Den ich verstehe hier die Frage nicht ganz. Ich kann mir nichts unter "Definieren Sie einen deterministischen, endlichen Automaten, der die Menge
[mm] L:={x_{i}x_{i}|1\le i \le n}* [/mm]
akzeptiert." vorstellen. Kann jemand ein Beispiel mit erklärung vorführen? Wäre sehr dankbar.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:44 So 01.06.2008 | | Autor: | New_Moon |
Hallo, bist du dir sicher, dass es heißt [mm]\Sigma = (x_i, x_i, \dots, x_n)[/mm] und nicht [mm]\Sigma = (x_1, x_i, \dots, x_n)[/mm]?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:10 So 01.06.2008 | | Autor: | Parkan |
Hi, danke für den Hinweis. Habe das jetzt korregiert. Bei der Menge L heisst das aber wirklich xi,xi |...
|
|
|
| |
|
Okay, ich versuche mich mal an der Aufgabe.
Das [mm]\Sigma[/mm] ist das Eingabealphabet des Automaten, [mm]L[/mm] ist die Sprache, die der Automat akzeptiert, d.h. jedes Wort aus L überführt den Automaten in den Endzustand. Der Automat befindet sich zu Beginn im Anfangszustand [mm]s_0[/mm].
Nehmen wir mal an, [mm]n = 3[/mm], dann ist [mm]\Sigma = {x_1, x_2, x_3[/mm] (= Eingabealphabet) und die Sprache, der der Automat akzeptiert ist [mm]L = {x_1 x_1, x_2 x_2, x_3 x_3}[/mm] (= Eingaben, die den Automaten in den Endzustand befördern). Du benötigst jetzt einen Anfangszustand ([mm]s_0[/mm]), einen Endzustand ([mm]s_4 (s_{n+1})[/mm]), einen Zustand aus dem der Automat (unabhängig von der Eingabe) nicht mehr rauskommt ([mm]s_5 (s_{n+2})[/mm]) und drei weitere Zustände ([mm]s_1, s_2, s_3[/mm]). Erhält der Automat im Anfangszustand eine Eingabe [mm]x_i[/mm], dann wechselt er in den Zustand [mm]s_i[/mm] (z.B. [mm]x_2, s_0 \to s_2[/mm]). Bekommt er in diesem Zustand wieder die Eingabe [mm]x_i[/mm], dann wechselt er in den Endzustand [mm]s_{n+1}[/mm]; erfolgt eine andere Eingabe, wechselt er in den Zustand [mm]s_{n+2}[/mm] und bleibt in diesem, egal was für eine Eingabe kommt.
Die einzelnen Zustände [mm]s_1, s_2, s_3[/mm] sind nötig, damit erkannt werden kann, ob zweimal die selbe Eingabe kam.
Zur Verdeutlichung kannst du dir ja trotzdem mal ein Zustandsübergangsdiagramm malen.
Was die konkrete Beantwortung der Fragestellung betrifft, bin ich mir auch nicht so sicher, was da alles reingehört. Die einzelnen Zustände [mm]s[/mm] kannst du auf jeden Fall erklären, vielleicht gehört auch die Zustandsübergangsfunktion [mm]\delta[/mm] (was ja nichts anderes, als das Diagramm in Worten ist) dazu?
|
|
|
|
