Knowunity
Schule. Endlich einfach.
Automaten
Automaten
Automaten
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
Automaten
Sarah •
Follow
116 Followers
-Mealy-Automaten -Deterministische endliche Automaten
Ähnliche Knows
S
8
Q3
17
13
2
Automaten
5
12/13
2
Automaten und Grammatiken Abi 2022
25
13
V
6
Akzeptor/MEALY/Moore Automat
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
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