• Increase font size
  • Default font size
  • Decrease font size

Automaten

E-Mail Drucken PDF

   Turingmaschine       Zelluläre Automaten

Ein Automat hat im weitesten Sinne die Eigenschaft, sein Verhalten selbst zu steuern. Eine Grundlage für diese Eigenschaft bilden Speicherelemente über die Automaten im Gegensatz zu Schaltnetzen verfügen. Diese Speicherelemente (Flip-Flops) verwalten innere Zustände des Automaten. Damit ist der Ausgang vom Eingang und vom inneren Zustand abhängig, während Schaltnetze eben nur vom Eingang abhängen. Es ist möglich und sinnvoll, den Automaten als algebraische Struktur aufzufassen. In der Literatur werden Automaten (z.B. Transduktoren) so als 6 - Tupel definiert.

Arten von Automaten

In verschiedenen Bereichen des täglichen Lebens werden Automaten benötigt. Gebräuchliche und einfach zu erfassende sind der Warenautomat oder auch Automaten, welche Eingaben erkennen und entsprechend reagieren. Geht man von endlichen Automaten aus, gibt es zwei Gruppen die in unterschiedlichen Kontexten Verwendung finden.

Akzeptoren

Akzeptoren werden in der Regel zur Spracherkennung eingesetzt. Sie signalisieren durch ihren jeweiligen Zustand die Richtigkeit eines Wortes. Ausgabealphabet und Ausgabefunktion entfallen, da nur akzeptierte Zustände erwartet werden. Der Automat liest also sequentiell die Zeichen des Übergabewortes. Eine Azeptanz liegt genau dann vor, wenn sich der Automat nach dem Lesen des letzten Zeichens in einem akzeptierten Zustand befindet.

Transduktoren

Auch hier unterscheidet man zwei Gruppen. Die erste Gruppe bezeichnet die Moore- Automaten. Diese sind dadurch gekennzeichnet, dass die Ausgabe des Automaten nur vom aktuellen Zustand abhängig ist. Die andere Gruppe beinhaltet die Automaten, deren Ausgabe vom Zustand und der Eingabe abhängig ist. Ein Fahrscheinautomat, der eine gültige Karte ausgibt, nachdem ausreichend Geld eingeworfen wurde, wäre also ein Moore Automat, da nur der Zustand relevant ist, bei dem der Nutzer den Schein erhält. Soll dagegen jedesmal ausgegeben werden, wieviel Geld noch fehlt, bzw. was bezahlt wurde, handelt es sich um einen Mealy - Automaten. Die Prüfung einer Zeichenkette auf Richtigkeit (mit einer entsprechenden Ausgabefunktion) entspräche ebenso einem Moore Automaten. In diesem Sinne können Akzeptoren als besondere Moore Automaten (ohne Ausgabe aufgefasst) werden.

Im Folgenden die Umsetzung eines einfachen DEA (deterministischer endlicher Automat in Python) zur Vokalerkennung in Wörtern :

 

01   class automat : 
02  
03   def __init__(self, wort) : 
04  
05                  self.index = 0 
06                  self.wort  = self.wort + '#' 
07  
08   def find (self, char)   : 
09  
10            while self.wort [self.index] != '#': 
11                  if self.wort [self.index] == char : return 1 
12                  self.index +=1 
13  
14            print "Fehler"     : 
15  
16   if __name__=="__main__":               : 
17  
18            wert=raw_input ("Eingabestring : ") 
19            test = automat (wert) 
20  
21            if find ('a'): 		# Zustand 1 
22              if find ('e'): 		# Zustand 2 
23                if find ('i'): 		# Zustand 3 
24                  if find ('o'): 		# Zustand 4 
25                    if find ('a'): 		# Zustand 5 
26  
27                               print "korrekt" 
 
[Source] 

      Script zur theoretischen Informatik

 Autoedit    Autoedit 958 kb

 

 

(c) g-ymnasium.de 2006 - 2013 + Administrator