System zur Simulation mathematischer Maschinen

Kurze Beschreibung der Automaten

 

 1.  Kleine Beschreibung des Endlichen Automaten

Ein (deterministischer, endlicher) Automat wird bildhaft gesprochen auf ein Eingabewort angesetzt und dieser 'erkennt' (oder 'akzeptiert') dieses Wort schließlich oder auch nicht. Die Menge der akzeptierten Wörter bildet dann die durch den Automaten  dargestellte oder definierte Sprache. Bei den Grammatiken war der Mechanismus in gewisser Weise umgekehrt: Die Grammatik 'erzeugt' durch entsprechende Regelanwendungen ein Wort. Das Wort der Sprache entsteht also erst am Ende des Erzeugungsprozesses. Jede durch den endlichen Automaten erkennbare Sprache ist "regulär.", 
 
 
 
 

2. Kleine Beschreibung des Keller Automaten

   
Mit dem Kellerautomat wird das Modell des endlichen Automaten so erweitert, daß dieses neue Automatenmodell genau die kontextfreien Sprachen erkennt. Dem endlichen Automaten mangelt es in irgend einer Form eines Speichers. Der endliche  Automat kann solche  Sprachen nicht erkennen, weil er zum Zeitpunkt, wenn er das Eingabezeichen $ erreicht, nicht mehr wissen kann, was a1,a2,a3...an war. Die einzige Information die ihm zur Verfügung steht, ist der Zustand, in dem er sich befindet. Der Kellerautomat besitzt einen Speicher, auf den jedoch nur in der Art eines Stacks, eines Kellers, zugegriffen werden kann. Die möglichen Aktionen eines Kellerautomaten hängen jetzt nicht nur vom Zustand und gelesenen Eingabezeichen ab, sondern auch vom Kellerinhalt (bzw. dem zur Zeit obersten Kellerzeichen). In jedem 'Rechenschritt' kann sich nicht nur der Zustand, sondern auch der Inhalt des Kellers verändern.
 
 
 
 
 

3. Kleine Beschreibung der Turingmaschine

 
Einfach beschrieben besteht die <Turingmaschine> aus einem unendlichen Band, das in Felder eingeteilt ist. Jedes Feld kann ein einzelnes Zeichen des sogenannten Arbeitsalphabets der Maschine enthalten. Auf dem Band kann sich ein Schreib- Lesekopf bewegen. Nur die Zeichen, auf denen sich der Kopf gerade befindet, können in dem aktuellen Rechenschritt verändert werden. Der Kopf kann in einem Rechenschritt um  max. eine Position nach links oder rechts bewegt werden. Bandfelder, die vom Schreib- Lesekopf noch nie besucht und verändert wurden, enthalten das Blank-Zeichen '$'.
 
 
 
 
 
 
Alan M. Turing, 1912-1954, englischer Mathematiker, Kryptoanalytiker und Computerkonstrukteur
System zur Simulation mathematischer Maschinen