Allgemeine Definition eines Automaten

02.04.2014, 14:45	Auf diesen Beitrag antworten »
ycraM	Allgemeine Definition eines Automaten Hallo, bin Informatikstudent im 1. Semester und habe mich bei einem Übungsblatt schon wacker bis zur letzten Teilaufgabe geschlagen. Habe leider keine Ahnung wie man diese korrekt und formal lösen kann und wäre sehr dankbar wenn mir jemand helfen könnte. Man soll die allgemeine Definition (ohne graphische Darstellung) eines endlichen Automaten angeben, welcher Binärzahlen n akzeptiert, die ohne Rest durch 2^k teilbar sind für alle k element N\{0} P.s : Falls ich in diesem Forum für solche Fragen falsch bin tut es mir leid. Lg, ycraM


03.04.2014, 10:51	Auf diesen Beitrag antworten »
Karlito	Hallo ycraM, Du bist hier genau richtig. Ich würde trotz der Aufgabenstellung den Automaten erst einmal zeichnen. Die Frage ist, was es denn für ein Automat sein soll. NEA oder DEA (bzw. NFA oder DFA mit den englischen Bezeichungen). Ich mache das mal exemplarisch für den NEA: Binärzahlen, welche ohne Rest durch 2 Teilbar sind bilden folgende Sprache: $[latex]<br /> L = \{10^k \| k \in \mathbb{N}\setminus \{0\} \}<br /> [/latex]$ Wir nehmen uns also einen Automaten, mit zwei Zuständen. S.Anhang. Dazu die formale Definition eines Automaten von Wikipedia: $[latex]<br /> A = \{Q,\Sigma,\Delta,S,F\}<br /> [/latex]$ Um den Automaten voll auszuspezifizieren müssen wir nun die Mengen $[latex]Q,\Sigma,\Delta,S[/latex]$ und definieren. ist die Menge der Zustände. In unserem Fall wäre das $[latex] Q = \{q_1,q_2\} [/latex]$ $[latex]\Sigma[/latex]$ ist das Eingabealphabet. In unserem Fall wäre das $[latex] \Sigma = \{0,1\} [/latex]$ $[latex]\Delta[/latex]$ ist die Übergangsrelation. Damit werden alle Transitionen im Automaten angegeben. Das macht man, indem man eine Menge von partiellen Übergangsfunktionen angibt. Für unseren Fall: $[latex] \Delta = \{ \delta(q_1,1) = q_2, \delta(q_2,0) = q_2 \} [/latex]$ . Man gibt also an, aus welchem Zustand sich mit welcher Eingabe welcher Folgezustand ergibt. ist der Startzustand. Das wäre bei uns Nun fehlt nur noch die Menge der Finalzustände . Da es hier nur einen Finalzustand gibt ist das trivialerweise $[latex] F = \{ q_2 \} [/latex]$ Damit ist der Automat voll spezifiziert. Ich hoffe das hilft. Wenn noch fragen sind, helfe ich gerne. VG, Karlito

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »