#!/usr/local/bin/perl
#
# [Turing_Simulator.pl] 28.03.1996 by R.Scholz <mrz@informatik.uni-jena.de>
#
# Beschreibung: simuliert eine Turing-Maschine.
#
# Aufruf: Turing_Simulator [Programm-Datei.tur [Eingabe-Band]]
#
# Übung 3, Aufgabe (1), Vorlesung PS
#
# Vereinbarungen:
#
# 1. Natürliche Zahlen sind unär kodiert: 1 --> 1
# 2 --> 11
# 3 --> 111 usw.
#
# 2. Bei Programmende sollte der Lesekopf am Anfang des Ergebniswortes stehen.
#
# 3. Das Band ist zweiseitig.
#
# 4. Es erfolgt keine Kontrolle, ob die Eingabewörter richtig sind;
# z.B. beim Programm 'add.tur' ist das Eingabeband '10101' zulässig,führt aber zum
# falschen Ergebnis '00111'. Man kann aber das 2. Wort durch 2 oder mehr Nullen
# nach rechts abgrenzen: '101001' erzeugt '001101'.
#
# 5. Die zulässigen Zeichen auf dem Band sind per Default '0' und'1'.
# Kann durch Variable $ALPHABET eingestellt werden bzw.
# durch 'ALPHABET {chars}' im Programmfile ( z.B.: ALPHABET 012RST )
# Das Eingabeband wird daraufhin geprüft.
#
# 6. Die Turingmaschine startet mit dem Anfangszustand $Start_Zustand=Start,
# der Kopf steht an Position 0;
# dort ist außerdem das Eingabeband abgespeichert.
# Das Programm wird bei Erreichen des Endzustandes $End_Zustand=Ende
# beendet.
printf "\n\n\t\tTuring_Simulator: Simulation einer Turing Maschine.\n\n";
printf "\t\t\t(C) 1996 mrz\@informatik.uni-jena.de\n\n\n";
printf "Aufruf: Turing_Simulator.pl [prog.tur [EB]] \n\n";
$Start_Zustand=Start;
$End_Zustand=Ende;
%ZUSTAENDE=(Start,"",Ende,""); # nur zur Anzeige für den Nutzer
$ALPHABET="01"; # zulässige Zeichen auf dem Band
%BAND=(); # das Arbeitsband
$AKT_ZUSTAND=$Start_Zustand; # aktueller Zustand der Turingmaschine bzw. des Programms,
# Startzustand festlegen.
$AKT_ZEICHEN=0; # gerade gelesenes Zeichen vom Arbeitsband
$STEPS=-1; # Anzahl der Schritte bis Programmende
# Ist die Schrittanzahl eine Interpretationsfrage ?
# -> was ist die Anzahl beim EB=0 ??
# 0 oder 1 ??
$KOPF_POS=0; # aktuelle Kopfposition
$LEFT_POS=$RIGHT_POS=0; # linke u. rechte Bandposition
$DIR=stop; # Richtung, in der der Kopf bewegt werden soll
$ZEICHEN=0; # zu schreibendes Zeichen
$ZUSTAND=0; # neuer anzunehmender Zustand
&check_input; # Eingabeparameter (file,band)
&read_turing_program; # Programm in Kontrolleinheit einlesen
&init_BAND; # Eingabeband auf Arbeitsband schreiben
printf "Programmfile: '$PROGRAM' \n";
printf "Eingabeband: '$EB' \n";
printf "Alphabet: '$ALPHABET' \n";
printf "Mögliche Zustände: ' ";
foreach (sort keys %ZUSTAENDE) { printf "$_ " }
printf "'\n\n";
#---------------------------------- Main loop ---------------------------------
do
{ $AKT_ZEICHEN=$BAND{$KOPF_POS}; &show_Zustand;
($DIR,$ZEICHEN,$ZUSTAND)=&return_KE($AKT_ZUSTAND,$AKT_ZEICHEN);
# test, ob die passende Regel vorhanden ist:
if ($ZEICHEN eq '')
{ printf "\nFehler bei Programmabarbeitung: keine Regel für: [Zustand='$AKT_ZUSTAND',Zeichen='$AKT_ZEICHEN'] ! \n";
die "(wahrscheinlich ist Ihr Programmfile '$PROGRAM' nicht korrekt.) \n\n";
}
# test, ob für den Zustand überhaupt eine Regel existiert:
if (not exists $ZUSTAENDE{$ZUSTAND})
{ printf "\nFehler bei Programmabarbeitung: keine Regel für: [Zustand='$ZUSTAND',Zeichen='$AKT_ZEICHEN'] ! \n";
die "(wahrscheinlich ist Ihr Programmfile '$PROGRAM' nicht korrekt.) \n\n";
}
$BAND{$KOPF_POS}=$ZEICHEN; # schreibe Zeichen auf akt. Kopfposition
if ($DIR eq right) # nach Rechts gehen ?
{ $KOPF_POS++;
if ($KOPF_POS > $RIGHT_POS) { $BAND{$KOPF_POS}=0; $RIGHT_POS++ }
}
elsif ($DIR eq left) # oder nach Links ?
{ $KOPF_POS--;
if ($KOPF_POS < $LEFT_POS) { $BAND{$KOPF_POS}=0; $LEFT_POS-- }
}
$AKT_ZUSTAND=$ZUSTAND; $STEPS++; # jetzt neuen Zustand annehmen
}
until ($AKT_ZUSTAND eq $End_Zustand); # besser als bei 'stop' abzubrechen.
&show_Zustand;
printf "\n$STEPS Schritte benötigt.\n\n";
# --------------------------------- Ende -------------------------------------
# ------------------------------ Subroutines ---------------------------------
sub check_input
# Behandlung der Kommandozeile, Default-Parameter setzen.
{
local $t;
if (@ARGV[0] ne "") # 1. Parameter
{
$t=@ARGV[0]; split(/\./,$t); $_=pop(@_); # endet Filename auf .tur ?
if ($_ eq tur)
{
$PROGRAM=$t;
die "\nFehler: Datei '$PROGRAM' nicht gefunden!\n" unless (-f $PROGRAM)
}
else
{
die "\nFehler: 1. Argument ('$t') muß Name des Programms sein und auf '.tur' enden !\n\n"
}
}
else { $PROGRAM="add.tur" }
if (@ARGV[1] ne "") # 2. Parameter
{
if (@ARGV[1] =~ /^[$ALPHABET]*$/) # Eingabeband aus $ALPHABET ?
{ $EB=@ARGV[1] }
else
{
die "\nFehler: 2. Argument ('@ARGV[1]') muß das Eingabeband sein, bestehend aus ^[$ALPHABET]*\$ !\n\n"
}
}
else { $EB=110111 }
}
sub read_turing_program
# liest das Turing-Programm aus der Datei $PROGRAM ein
# und erzeugt daraus die Kontrolleinheit KE
{
local $line;
local $Z,$gz,$ri,$sz,$nz;
open(PROG,$PROGRAM) || die "\nFehler: Kann Programm-Datei '$PROGRAM' nicht öffnen!\n\n";
while (chomp($line=<PROG>))
{
next if ($line =~ /^#/); # skip comments
if ($line =~ /^(ALPHABET)/)
{
split(/\s/,$line);
$ALPHABET=shift(@_);$ALPHABET=shift(@_);
next;
}
($Z,$gz,$ri,$sz,$nz)=split(/\s/,$line); # split at whitespaces
next if ($ri !~ /(stop)|(right)|(left)/); # read only turing-commands
if (index($ALPHABET,$gz) == -1) # $gz korrekt ?
{ printf "Fehler in folgender Zeile des Programms '$PROGRAM' :\n\n";
printf "\t$line \n\n";
die "Das Zeichen '$gz' ist nicht im zulässigen Alphabet '$ALPHABET' enthalten !\n\n";
}
# $AAA=quotemeta $ALPHABET;
if (index($ALPHABET,$sz) == -1) # $sz korrekt ?
{ printf "Fehler in folgender Zeile des Programms '$PROGRAM' :\n\n";
printf "\t$line \n\n";
die "Das Zeichen '$sz' ist nicht im zulässigen Alphabet '$ALPHABET' enthalten !\n\n";
}
if (length($Z) >8)
{ printf "Fehler in folgender Zeile des Programms '$PROGRAM' :\n\n";
printf "\t$line \n\n";
die "Die Länge des Zustandes '$Z' ist zu groß (>8) !\n\n";
}
if (length($nz) >8)
{ printf "Fehler in folgender Zeile des Programms '$PROGRAM' :\n\n";
printf "\t$line \n\n";
die "Die Länge des Zustandes '$nz' ist zu groß (>8) !\n\n";
}
$KE{$Z,$gz}="$ri,$sz,$nz"; # Aufbau der Kontrolleinheit
$ZUSTAENDE{$Z}=""; # zur Ausgabe aller
# möglichen Zustände
}
close PROG;
}
sub return_KE
# input: Zustand + gelesenes Zeichen
# output: Richtung,zu schreibenes Zeichen, neuer Zustand
{
local ($zustand,$zeichen)=@_;
split(/,/,$KE{$zustand,$zeichen});
}
sub init_BAND
# belegt das Band mit dem Eingabeband EB
# %BAND muß nicht mit 0 initialisiert werden, das passiert automatisch,
# wenn das Band vergrößert wird (siehe Main-loop)
{
local $i;
$i=length($EB)-1;
for (0..$i) { $BAND{$_}=substr($EB,$_,1) }
$RIGHT_POS=$i;
}
sub show_Zustand
# Zeigt den Zustand während der Programmabarbeitung an
{
printf "Zustand = [$AKT_ZUSTAND]";
for (1..(10-length($AKT_ZUSTAND))) { printf " " }
printf "AB = [";
for ($LEFT_POS..$RIGHT_POS) { printf "$BAND{$_}" }
printf "]\nKopf:\t\t\t ";
for (1..($KOPF_POS-$LEFT_POS )) { printf " " }
printf "#\n";
}