kurse:ef05a-2021:turingmaschinen:tm-doc [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Beispiele ======
<code txt unaryplusone.txt>
#tape 1111

# Addiert 1 zu einer unären zahl
# Die Maschine stoppt am Anfang der Zahl.


# Vorwärts bis zum ersten . Schreibe dort eine 1, gehe nach links und mache fertig
start
  . 1 L fertig

# Rückwärts bis zum ersten . Dann rechts und stop.
fertig L
  . . R stop


</code>

<code txt bla.txt>
# Schreibt bla ;-)

# {...} Beinhaltet Kommandos der Form Px, um den Buchstaben x zu schreiben, oder R,L, um den Kopf zu bewegen.
# Damit werden eine ganze Reihe von Zuständen generiert.
start
   . {Pb R Pl R Pa L L} stop
   
</code>
===== Spezifikation (sort of) =====
==== Spezialzeichen ====
Folgende Zeichen dürfen nicht als Symbole auf dem Band verwendet werden:
  * Leerzeichen (Trennsymbol)
  * ''.'' Blank
  * ''*'' (wildcard)
  * ''@'' (Symbolvariable in m-Funktion oder m-Aufruf)
  * ''\$'' (Zustandsvariable)
  * ''['' und '']'' (Symbolbereich)
  * ''_'' (underscore, wird intern verwendet)
  * ''#'' Beginn eines Kommentars
==== Syntax ====
=== Kommentare und Band-Definition ===

  * Zeilen, die mit # beginnen sind Kommentar, ausser nach ''#tape'' folgen die Symbole, die beim Start auf dem Band geschrieben sind.

=== Zustände ===

  * Die Zustände sind durch eine Leerzeile getrennt.
  * Der default ist das Zeichen lassen und nach rechts gehen. Die default-Richtung kann nach dem Zustandsnamen angegeben werden. Danach kann zusätzlich ein default-Zustand angegeben werden (wenn von diesem verschieden).
  * Für ein Zeichen ''read'' kann in einem Zustand folgendes definiert werden:
    * ''read write dir state'', wobei dir auch 'N' für nicht bewegen sein kann.
    * ''read {c1 c2 ...} state'', wobei ''c1, c2'' etc. Kommandos 'R' für rechts, 'L' für links und 'Px' für ein x aufs Band schreiben ist.
  * Es ist möglich, für ''read'' einen Bereich von Zeichen mit ''[xyz]'' anzugeben (nur Symbolen, keine @1 etc.), oder ''*'' für alle möglichen Zeichen.
  * Wird für ''write'' ein ''*'' verwendet bezieht sich das auf das gelesene Zeichen.

=== m-Funktionen ===
  * Header: ''@name(x ; y )''
    * wobei x die Anzahl der zu übergebenden Symbole als Argumente ist und
    * y die Anzahl der zu übergebenden Zustände ist.
  * Body: Menge von lokalen Zustandsdefinitionen. Diese können ''@1'', ''@2'', etc. als übergebene Symbole und ''$1'', ''$2'' als übergebene Zustände enthalten.
    * Die Zustände sollten global eindeutige Namen haben (ausser Sie werden nur lokal in der m-Funktion verwendet).
    * Typischerweise wird ein Zustand übergeben, zu dem die Funktion «zurückkehren» soll, wenn sie fertig ist.
  * Footer: ''@end''


{{kurse:ef05a-2021:turingmaschinen:tm_d.pdf|Slides vom Turing-Maschinen-Kurs der Uni Fribourg}}