Informatik /

Automaten

Automaten

 DETERMINISTISCHE ENDLICHE AUTOMATEN
DEFINITION
Ein Automat heißt deterministisch, wenn für jeden
seiner Zustände für jedes Eingabezeichen n

Automaten

user profile picture

Sarah

116 Followers

Teilen

Speichern

36

 

12

Lernzettel

-Mealy-Automaten -Deterministische endliche Automaten

Nichts passendes dabei? Erkunde andere Fachbereiche.

DETERMINISTISCHE ENDLICHE AUTOMATEN DEFINITION Ein Automat heißt deterministisch, wenn für jeden seiner Zustände für jedes Eingabezeichen nur genau ein Folgezustand existiert. Das Verhalten des Automaten ist somit eindeutig bestimmt. REDUZIERTER UBERGANGSGRAPH Alle Übergange, die nicht in den akzeptierenden Zu- stand führen können, werden gestrichen. Alle nicht aufgeführten Übergänge führen in einen Fehlerzustand. KONFIGURATION Bearbeitung eines Wortes lässt sich als Folge von Konfigurationen darstellen, die der Automat nacheinander annimmt Konfiguration besteht aus aktuellem Zustand und der noch zu verarbeitenden Ausgabe Die Menge an Wörter, die vom Automaten ak- zeptiert werden, also die Wörter, bei denen der Automat in einen akzeptierenden Endzustand gelangt, nennt man die vom Automaten akzep- tierte Sprache Bsp: (a., EE) → (9₂, E) → (q4, €) → L-{EE,...} START qº E ENDLICHE AUTOMATEN Automaten werden als endlich bezeichnet, da die Menge der Eingaben, der Ausgaben und Zustande, K→ q₁ die sie durchlaufen, endlich ist die Verarbeitung der Eingabe erfolgt im Inneren des Automaten die Eingabemöglichkeiten sind begrenzt und müssen in der korrekten Reihenfolge erfolgen Computer verarbeiten Zeichenfolgen eines Alphabets, dafür ist ein Eingabe- & Ausgabealphabet nötig ein Automat besitzt verschiedene Zustände, über eine Zustandsmenge wird gespeichert, welche Eingabe bisher getätigt wurde die Übergangsfunktion gibt an, was welche Eingabe in welchem Zustand bewirkt ↳ legt die zeitliche Abfolge der Ereignisse fest → Ausgabefunktion gibot an, welche Ausgabe durch die jeweilige Eingabe in einem Zustand ausgelöst wird UBERGANGSFUNKTION M ao 9₂₁ ao 9₁ AUSGABEFUNKTION M € E START go 9₁ H/E K→ 9₂ 9₂₁ E H ao ÜBERGANGSGRAPH M/E H/B ao AKZEPTOREN-ERKENNENDE AUTOMATEN deterministisch, wenn für jeden seiner Zustände für...

Mit uns zu mehr Spaß am Lernen

Hilfe bei den Hausaufgaben

Mit dem Fragen-Feature hast du die Möglichkeit, jederzeit Fragen zu stellen und Antworten von anderen Schüler:innen zu erhalten.

Gemeinsam lernen

Mit Knowunity erhältest du Lerninhalte von anderen Schüler:innen auf eine moderne und gewohnte Art und Weise, um bestmöglich zu lernen. Schüler:innen teilen ihr Wissen, tauschen sich aus und helfen sich gegenseitig.

Sicher und geprüft

Ob Zusammenfassungen, Übungen oder Lernzettel - Knowunity kuratiert alle Inhalte und schafft eine sichere Lernumgebung zu der Ihr Kind jederzeit Zugang hat.

App herunterladen

Alternativer Bildtext:

jedes Eingabezeichen nur ein Folgezustand existiert (Verhalten eindeutig bestimmt! entscheidet, ob eine Eingabe über dem Eingabealphabet korrekt ist, Ausgabe ist unwichtig, nur Zustände definieren, die bei konekter Fingabe folgen es muss eine Spezifikation eines Problems vorliegen, anhand derer sich das Problem als deterministischer Automat formulieren lässt ein deterministischer endlicher Automat hat keine Wahlmöglichkeiten für den Zustandswechsel bei einer konkreten Gingabe Formal definiert man einen deterministischen Automaten als S-Tupel (ohne Ausgabealphabet oder Ausgabefunktion jedoch mit F der Menge an akzeptierenden Endzuständen, wobei Feine Teilmenge von Q ist ↳ H E 8 E M/E MEALY-AUTOMAT Mealy-Automaten, die eine Eingabe in eine Ausgabe transformieren, werden als Transduktoren bezeichnet. Formal definiert als 6-Tupel IQ, s, E,S2,8, 21: -K 93 Q ist eine nicht leere, endliche Menge an Zuständen SEQ ist der Startzustand E ist ein nicht leeres, endliches Eingabealphabet → ist ein nicht leeres, endliches Ausgabealphabet → 8: QxE →Q ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Ginga- bezeichen einen Nachfolgezustand zuordnet →2: QxE →→ ist die Ausgabefunktion, die jeder Kombination aus einem Zustand und einem Einga- bezeichen eine Ausgabe zuordnet K→ qu E E,K E,K GRIECHISCHE BUCHSTABEN 95 qu ist der über die Anforderung definierte Endzustand q stellt eine Fehlersenke/Fehlerzustand dar (aus diesem Zustand kann man nicht mehr in einen akzeptierenden Endzustand gelangen) Σ Sigma Omega 8 Delta λ Lambda @ Omega E Epsilon E,K

Informatik /

Automaten

user profile picture

Sarah   

Follow

116 Followers

 DETERMINISTISCHE ENDLICHE AUTOMATEN
DEFINITION
Ein Automat heißt deterministisch, wenn für jeden
seiner Zustände für jedes Eingabezeichen n

App öffnen

-Mealy-Automaten -Deterministische endliche Automaten

Ähnliche Knows

S

8

Q3

Know Q3 thumbnail

17

 

13

user profile picture

2

Automaten

Know Automaten thumbnail

5

 

12/13

user profile picture

2

Automaten und Grammatiken Abi 2022

Know Automaten und Grammatiken Abi 2022 thumbnail

25

 

13

V

6

Akzeptor/MEALY/Moore Automat

Know Akzeptor/MEALY/Moore Automat thumbnail

8

 

12

DETERMINISTISCHE ENDLICHE AUTOMATEN DEFINITION Ein Automat heißt deterministisch, wenn für jeden seiner Zustände für jedes Eingabezeichen nur genau ein Folgezustand existiert. Das Verhalten des Automaten ist somit eindeutig bestimmt. REDUZIERTER UBERGANGSGRAPH Alle Übergange, die nicht in den akzeptierenden Zu- stand führen können, werden gestrichen. Alle nicht aufgeführten Übergänge führen in einen Fehlerzustand. KONFIGURATION Bearbeitung eines Wortes lässt sich als Folge von Konfigurationen darstellen, die der Automat nacheinander annimmt Konfiguration besteht aus aktuellem Zustand und der noch zu verarbeitenden Ausgabe Die Menge an Wörter, die vom Automaten ak- zeptiert werden, also die Wörter, bei denen der Automat in einen akzeptierenden Endzustand gelangt, nennt man die vom Automaten akzep- tierte Sprache Bsp: (a., EE) → (9₂, E) → (q4, €) → L-{EE,...} START qº E ENDLICHE AUTOMATEN Automaten werden als endlich bezeichnet, da die Menge der Eingaben, der Ausgaben und Zustande, K→ q₁ die sie durchlaufen, endlich ist die Verarbeitung der Eingabe erfolgt im Inneren des Automaten die Eingabemöglichkeiten sind begrenzt und müssen in der korrekten Reihenfolge erfolgen Computer verarbeiten Zeichenfolgen eines Alphabets, dafür ist ein Eingabe- & Ausgabealphabet nötig ein Automat besitzt verschiedene Zustände, über eine Zustandsmenge wird gespeichert, welche Eingabe bisher getätigt wurde die Übergangsfunktion gibt an, was welche Eingabe in welchem Zustand bewirkt ↳ legt die zeitliche Abfolge der Ereignisse fest → Ausgabefunktion gibot an, welche Ausgabe durch die jeweilige Eingabe in einem Zustand ausgelöst wird UBERGANGSFUNKTION M ao 9₂₁ ao 9₁ AUSGABEFUNKTION M € E START go 9₁ H/E K→ 9₂ 9₂₁ E H ao ÜBERGANGSGRAPH M/E H/B ao AKZEPTOREN-ERKENNENDE AUTOMATEN deterministisch, wenn für jeden seiner Zustände für...

Nichts passendes dabei? Erkunde andere Fachbereiche.

Mit uns zu mehr Spaß am Lernen

Hilfe bei den Hausaufgaben

Mit dem Fragen-Feature hast du die Möglichkeit, jederzeit Fragen zu stellen und Antworten von anderen Schüler:innen zu erhalten.

Gemeinsam lernen

Mit Knowunity erhältest du Lerninhalte von anderen Schüler:innen auf eine moderne und gewohnte Art und Weise, um bestmöglich zu lernen. Schüler:innen teilen ihr Wissen, tauschen sich aus und helfen sich gegenseitig.

Sicher und geprüft

Ob Zusammenfassungen, Übungen oder Lernzettel - Knowunity kuratiert alle Inhalte und schafft eine sichere Lernumgebung zu der Ihr Kind jederzeit Zugang hat.

App herunterladen

Knowunity

Schule. Endlich einfach.

App öffnen

Alternativer Bildtext:

jedes Eingabezeichen nur ein Folgezustand existiert (Verhalten eindeutig bestimmt! entscheidet, ob eine Eingabe über dem Eingabealphabet korrekt ist, Ausgabe ist unwichtig, nur Zustände definieren, die bei konekter Fingabe folgen es muss eine Spezifikation eines Problems vorliegen, anhand derer sich das Problem als deterministischer Automat formulieren lässt ein deterministischer endlicher Automat hat keine Wahlmöglichkeiten für den Zustandswechsel bei einer konkreten Gingabe Formal definiert man einen deterministischen Automaten als S-Tupel (ohne Ausgabealphabet oder Ausgabefunktion jedoch mit F der Menge an akzeptierenden Endzuständen, wobei Feine Teilmenge von Q ist ↳ H E 8 E M/E MEALY-AUTOMAT Mealy-Automaten, die eine Eingabe in eine Ausgabe transformieren, werden als Transduktoren bezeichnet. Formal definiert als 6-Tupel IQ, s, E,S2,8, 21: -K 93 Q ist eine nicht leere, endliche Menge an Zuständen SEQ ist der Startzustand E ist ein nicht leeres, endliches Eingabealphabet → ist ein nicht leeres, endliches Ausgabealphabet → 8: QxE →Q ist die Übergangsfunktion, die jeder Kombination aus einem Zustand und einem Ginga- bezeichen einen Nachfolgezustand zuordnet →2: QxE →→ ist die Ausgabefunktion, die jeder Kombination aus einem Zustand und einem Einga- bezeichen eine Ausgabe zuordnet K→ qu E E,K E,K GRIECHISCHE BUCHSTABEN 95 qu ist der über die Anforderung definierte Endzustand q stellt eine Fehlersenke/Fehlerzustand dar (aus diesem Zustand kann man nicht mehr in einen akzeptierenden Endzustand gelangen) Σ Sigma Omega 8 Delta λ Lambda @ Omega E Epsilon E,K