Informatiker Board | Automatentheorie | Allgemeine Definition eines Automaten

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Allgemeine Definition eines Automaten

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Allgemeine Definition eines Automaten

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

ycraM
Grünschnabel

Dabei seit: 02.04.2014
Beiträge: 1

Allgemeine Definition eines Automaten

Zitatantwort auf diesen Beitrag erstellen

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

02.04.2014 14:45

Nehmen Sie ycraM in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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 [latex]F[/latex]

definieren.

[latex]Q[/latex]

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.
[latex]S[/latex]

ist der Startzustand. Das wäre bei uns [latex] S = q_1 [/latex]

Nun fehlt nur noch die Menge der Finalzustände [latex]F[/latex]

. 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

Karlito hat dieses Bild (verkleinerte Version) angehängt:

03.04.2014 10:51

Nehmen Sie Karlito in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Allgemeine Definition eines Automaten