AZreferate - Referate und hausaufgaben fur schule.
Referatesuche, Hausarbeiten und Seminararbeiten Kostenlose Online-Dokumente mit Bildern, Formeln und Grafiken. Referate, Facharbeiten, Hausarbeiten und Seminararbeiten findest für Ihre einfache Hausarbeiten.



BetriebstechnikBiographienBiologieChemieDeutschDigitaltechnik
ElectronicaEpochenFertigungstechnikGemeinschaftskundeGeographieGeschichte
InformatikKulturKunstLiteraturManagementMathematik
MedizinNachrichtentechnikPhilosophiePhysikPolitikProjekt
PsychologieRechtSonstigeSportTechnikWirtschaftskunde

Referat ENDLICHE AUTOMATEN - Erkennender Automat, Allgemeine endliche Automaten

informatik referate

informatik referate

ENDLICHE AUTOMATEN

  1. Einleitung - Was ist ein endlicher Automat ?
  2. Erkennender Automat
  3. Zustandstabellen
  4. Allgemeine endliche Automaten
  5. Mustersuche mittels Automaten
  6. Programmierung von Automaten
  7. FOLIEN

1) Einleitung - Endliche Automaten

Ein endlicher Automat ist ein Modell zur Beschreibung von sogenannten zustandsabhängigen Systemen. Merkmale:

  • System befindet sich immer in einem bestimmten Zustand (es gibt endlich viele unterschiedliche Zustände)
  • Es gibt Eingaben, die bewirken, dass das System seinen Zustand wechselt
  • Ein Automat verarbeitet Symbole aus dem Eingabealphabet (endlich viele)
  • Regeln, welcher Folgezustand aufgrund des aktuellen Zustandes und des nächsten Eingabesymbols eingenommen werden soll
  • Graphische Darstellung durch sogenannte Zustandsdiagramme
  • endliche Automaten entsprechen einer regulären Grammatik (links - Hilfssymbol; rechts - Grundsymbol oder Hilfssymbol)
  • es gibt 2 Arten von endlichen Automaten:
    • Allgemeine Automaten
    • Erkennende Automaten

Zurück zum Start!

2) Erkennender Automat - Endliche Automaten

Beispiel

Beispiel: Erkenne eine Festkommazahl
Erlaubt sind: 3.14 +.15 -.3 +5.987 -0.321
Eingangsalphabet: Zahlen 0-9, +, -, .

Grundsätzlicher Algorithmus

(vom Startzustand beginnend)

solange Eingabesymbol vorhanden
entsprechenden Folgezustand einnehmen (aufgrund des aktuellen Zustandes + Eingabesymbol)
end-solange
wenn 'Endzustand' erreicht
Eingabe war richtig
sonst
Eingabe war falsch
end-wenn

Reguläre Grammatik

Jedem Automat entspricht eine reguläre Grammatik und umgekehrt.
Beispiel (entspricht dem ersten Beispiel)
S -> 0A / 1A / 2A / 3A / 4A / 5A / 6A / 7A / 8A / 9A / .B
S -> +D / -D
A -> 0A / 1A / 2A / 3A / 4A / 5A / 6A / 7A / 8A / 9A / .B / (Ende)
B -> 0C / 1C / 2C / 3C / 4C / 5C / 6C / 7C / 8C / 9C
C -> 0C / 1C / 2C / 3C / 4C / 5C / 6C / 7C / 8C / 9C / (Ende)
D -> 0A / 1A / 2A / 3A / 4A / 5A / 6A / 7A / 8A / 9A / .B

Beispiel: +.15
S -> +D -> +.B -> +.1C -> +.15C -> +.15 (Ende)

Zustandsdiagramm (Transitionsgraph)
  • gerichteter Graph
  • Knoten
    • entsprechen den Zuständen des Systems
    • Beschreibung des Zustands sollte möglich sein
    • Bezeichnung: S0, S1, A, B,
    • genau ein Startzustand
    • ein oder mehrere Endzustande
  • Kanten
    • jede Kante entspricht einem Eingabesymbol
    • Wechsel von 'Si' zu 'Sj' wenn a eingegeben wird
    • Mehrfachkanten erlaubt
  • unvollständiger Automat: es gibt Knoten wo Kanten fehlen

bei absichtlichen Fehlern: fehlende Kanten führen zu Fehlerzustand (Falle)

  • allgemeine endliche Automaten erzeugen auf Grund eines Eingabesymbols und abhängig vom momentanten Zustand ein bestimmtes Ausgabesymbol und nehmen darauf den Folgezustand ein.

Zurück zum Start!

3) Zustandstabellen - Endliche Automaten

  • Statt eines Graphen kann eine Tabelle für die Beschreibung eines Automaten verwendet werden
  • Grundlage für die tabellengesteuerte Programmierung

Zurück zum Start!

4) Allgemeine endliche Automaten - Endliche Automaten

  • Zusätzlich zum Analysieren einer Eingabe
  • Ausführen von semantischen Aktionen

Beispiel Paralleladdierer

Zustände:
S .. Startzustand (ohne Übertrag)
U .. Übertrag

Zurück zum Start!

5) Mustersuche mittels Automaten - Endliche Automaten

  • Bei Textverarbeitung
  • Bilddatenverarbeitung
  • Digitale Tonaufnahme

Beispiel: Suche eine Zeichenfolge B[1m] in einer anderen Zeichenfolge A[1n]
Primitive Lösung

for ( i=1; (i<=m)&&(A[j]==B[k]; j++,k++);
if(k==m+1) gefunden=1;

Aufwand: n*m Schritte
Suche mittels Automat
Aufwand: n+m Schritte
Suche erfolgt in 2 Schritten:

  1. Konstruktion des Automaten durch das Suchprogramm
  2. Eigentliche Suche mittels Automat

E=
Suche 'aabaabb'

Skelettautomat
erweiterter Automat

Zurück zum Start!

6) Programmierung von Automaten - Endliche Automaten

Die Programme beziehen sich auf die Zustandstabelle in Punkt 3!

Programmgesteuert

Pseudocode:

Zustand = S       // Startzustand
solange (Eingabesymbol <> Ende)
case Zustand
wenn S:
case Eingabesymbol
wenn Ziffer: Zustand A
wenn Punkt: Zustand B
wenn +/-: Zustand D
wenn A:
case Eingabesymbol
wenn Ziffer: Zustand A
wenn Punkt: Zustand B
wenn B:
case Eingabesymbol
wenn Ziffer: Zustand C
.
.
.
   end-case
end-solange

wenn (Zustand = A oder Zustand = C)
alles in Ordnung
sonst
ist ein Fehler aufgetreten (möglicherweise Falle einbauen!)
end-wenn


Semantische Aktionen können im jeweiligen CASE-Zweig realisiert werden.
Vorteile:

  • sehr leicht verständlich
  • für Speziallösungen geeignet

Nachteile:

  • umfangreicher Programmcode
  • jeder Automat ist neu zu programmieren
Tabellengesteuert

Die Funktion des Automaten wird mit Hilfe von zweidimensionalen Arrays verwirklicht, wobei die Elemente die jeweiligen Folgezustände enthalten.
Definitionen der Konstanten (Zustände und Eingabesymbole)
z.B. S = 0; A = 1; B = 2; C = 3; D = 4;
Ziffer = 0; Punkt = 1; +/- = 2;

ZustandsTab[][4]=, , , , } //Tabellendefinition
Pseudocode

Zustand = S
solange (Eingabesymbol <> Ende)
Zustand = ZustandsTab[Zustand][Eingabesymbol]
end-solange

wenn (Zustand = A)
alles in Ordnung
sonst
ist ein Fehler aufgetreten (Falle!)
end-wenn


Semantische Aktionen werden mit Hilfe eines Zusatzes über die gewünschte Aktion beim Element gespeichert. Dieser Zusatz ist entweder eine Zahl, die die Aktion bezeichnet, oder ein Zeiger auf die gewünschte Funktion.

Zurück zum Start!

FOLIEN

Endliche AUTOMATEN

Erkennender Automat

Zustandsdiagramm

Eingangsalphabet: Zahlen 0-9, +, -, .

Grundsätzlicher Algorithmus

solange Eingabesymbol vorhanden
entsprechenden Folgezustand einnehmen (aufgrund des aktuellen Zustandes + Eingabesymbol)
end-solange
wenn 'Endzustand' erreicht
Eingabe war richtig
sonst
Eingabe war falsch
end-wenn

Reguläre Grammatik

S -> 0A / 1A / 2A / 3A / 4A / 5A / 6A / 7A / 8A / 9A / .B
S -> +D / -D
A -> 0A / 1A / 2A / 3A / 4A / 5A / 6A / 7A / 8A / 9A / .B / (Ende)
B -> 0C / 1C / 2C / 3C / 4C / 5C / 6C / 7C / 8C / 9C
C -> 0C / 1C / 2C / 3C / 4C / 5C / 6C / 7C / 8C / 9C / (Ende)
D -> 0A / 1A / 2A / 3A / 4A / 5A / 6A / 7A / 8A / 9A / .B

Zurück zum Start!

Zustandstabellen

Allgemeine endliche Automaten

Beispiel Paralleladdierer


Zurück zum Start!

Mustersuche mittels Automaten

Beispiel: Suche eine Zeichenfolge B[1m] in einer anderen Zeichenfolge A[1n]
Primitive Lösung

for ( i=1; (i<=m)&&(A[j]==B[k]; j++,k++);
if(k==m+1) gefunden=1;

Aufwand: n*m Schritte

Suche mittels Automat

Aufwand: n+m Schritte
Suche 'aabaabb'

Skelettautomat
erweiterter Automat

Zurück zum Start!

Programmierung von Automaten

Programmgesteuert

Pseudocode:

Zustand = S       // Startzustand
solange (Eingabesymbol <> Ende)
case Zustand
wenn S:
case Eingabesymbol
wenn Ziffer: Zustand A
wenn Punkt: Zustand B
wenn +/-: Zustand D
wenn A:
case Eingabesymbol
wenn Ziffer: Zustand A
wenn Punkt: Zustand B
.
.
.
   end-case
end-solange

wenn (Zustand = A oder Zustand = C)
alles in Ordnung
sonst
ist ein Fehler aufgetreten (möglicherweise Falle einbauen!)
end-wenn
Tabellengesteuert

Definitionen der Konstanten (Zustände und Eingabesymbole)
S = 0; A = 1; B = 2; C = 3; D = 4;
Ziffer = 0; Punkt = 1; +/- = 2;

ZustandsTab[][4]=, , , , } //Tabellendefinition
Pseudocode

Zustand = S
solange (Eingabesymbol <> Ende)
Zustand = ZustandsTab[Zustand][Eingabesymbol]
end-solange

wenn (Zustand = A)
alles in Ordnung
sonst
ist ein Fehler aufgetreten (Falle!)
end-wenn



Referate über:


Datenschutz




Copyright © 2024 - Alle Rechte vorbehalten
AZreferate.com
Verwenden sie diese referate ihre eigene arbeit zu schaffen. Kopieren oder herunterladen nicht einfach diese
# Hauptseite # Kontact / Impressum