From:	SMTP%"sboden@wins.uia.ac.be" 20-FEB-1995 09:18:27.92
To:	USRC
CC:	
Subj:	v47i071: tursim - A Turing Machine, Part01/01

Resent-Date: 18 Feb 1995 20:22:09 -0600
Path: decwrl!enews.sgi.com!lll-winken.llnl.gov!uwm.edu!cs.utexas.edu!uunet!sparky!not-for-mail
From: sboden@wins.uia.ac.be (Sven Boden)
Newsgroups: comp.sources.misc
Subject: v47i071: tursim - A Turing Machine, Part01/01
Followup-To: comp.sources.d
Date: 18 Feb 1995 20:22:09 -0600
Organization: Sterling Software
Lines: 1848
Sender: kent@sparky.sterling.com
Approved: kent@sparky.sterling.com
Message-Id: <3i6a0h$2pp@sparky.sterling.com>
Nntp-Posting-Host: sparky.sterling.com
X-Md4-Signature: ca61c75ac9dc20d19ec204d36d4db8a5
To: unix-sources@pa.dec.com
Resent-Message-Id: <"H_SOA1.0._12.a0hHl"@ftp-gw-1.pa.dec.com>
Resent-From: unix-sources@pa.dec.com
X-Mailing-List: <unix-sources@pa.dec.com> archive/latest/490
X-Loop: unix-sources@pa.dec.com
Precedence: list
Resent-Sender: unix-sources-request@pa.dec.com

Submitted-by: sboden@wins.uia.ac.be (Sven Boden)
Posting-number: Volume 47, Issue 71
Archive-name: tursim/part01
Environment: ANSI-C

This archive contains the ANSI-C sources of a Turing machine + a few
examples.

Herman Horsten && Sven Boden
---
#! /bin/sh
# This is a shell archive.  Remove anything before this line, then feed it
# into a shell via "sh file" or similar.  To overwrite existing files,
# type "sh file -c".
# Contents:  tursim tursim/README tursim/findnext.inp
#   tursim/findnext.tur tursim/makefile tursim/not.inp tursim/not.tur
#   tursim/oddeven.inp tursim/oddeven.tur tursim/tape.c tursim/tape.h
#   tursim/trans.c tursim/trans.h tursim/turing.c tursim/turing.h
#   tursim/tursim.c tursim/tursim.mak tursim/tursim.man
# Wrapped by kent@ftp on Sat Feb 18 20:19:54 1995
PATH=/bin:/usr/bin:/usr/ucb:/usr/local/bin:/usr/lbin:$PATH ; export PATH
echo If this archive is complete, you will see the following message:
echo '          "shar: End of archive 1 (of 1)."'
if test ! -d 'tursim' ; then
    echo shar: Creating directory \"'tursim'\"
    mkdir 'tursim'
fi
if test -f 'tursim/README' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/README'\"
else
  echo shar: Extracting \"'tursim/README'\" \(1647 characters\)
  sed "s/^X//" >'tursim/README' <<'END_OF_FILE'
XTursim is Copyright (C) 1994 by Sven Boden && Herman Horsten, Belgium.
XAll rights reserved.  Permission is granted to freely distribute
Xthis as long as this copyright message is retained intact.
XPermission to distribute this as part of a commercial product
Xrequires explicit permission of the authors.
X
X
XThis archive contains the ANSI-C sources for a Turing-machine. It was
Xwritten as a project for a computer science course at the University of 
XAntwerp (RUCA/UIA) a couple of years ago. 
X
XAuthors: (2 last year computer science students 94/95)
X  Sven Boden
X  Paviljoenweg 9
X  2910 Essen (Belgium)
X  Tel: 03/667.27.37
X  sboden@wins.uia.ac.be
X
X  Herman Horsten
X  Hertenstraat 9
X  2300 Turnhout (Belgium)
X  Tel: 014/41.01.24
X  horsten@wins.uia.ac.be
X
X---
X
XREAD     ME     This file
XFINDNEXT TUR    Turing machine that finds the second occurence of the first ch
XODDEVEN  TUR    Turing machine that tells whether binary number is odd or even
XNOT      TUR    Turing machine that shows the use of ~x
XTAPE     H      Representation of tape
XTAPE     C
XTRANS    H      Representation of transition-matrix
XTRANS    C
XTURING   H      Representation of turing machine
XTURING   C
XTURSIM   C      Main program of tursim
XTURING   MAK    Make-file for UNIX
XTURSIM   MAK    Make-file for MS-DOS (Turbo-C++ V3.1)
XTURSIM   MAN    Manual in ASCII-format
XTURSIM   NED    Manual in Dutch
X---
X* If God wanted us to think in hexadecimal, he would have given us 16 fingers
X* Don't burn your bridges after crossing, you may have to backtrack someday
X* You only need your body to carry your brain around
X* Don't love one, don't love two, but love the one who loves you too
END_OF_FILE
  if test 1647 -ne `wc -c <'tursim/README'`; then
    echo shar: \"'tursim/README'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/README'
  # end of 'tursim/README'
fi
if test -f 'tursim/findnext.inp' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/findnext.inp'\"
else
  echo shar: Extracting \"'tursim/findnext.inp'\" \(23 characters\)
  sed "s/^X//" >'tursim/findnext.inp' <<'END_OF_FILE'
Xx....yyyyy....xyyyyyxx
END_OF_FILE
  if test 23 -ne `wc -c <'tursim/findnext.inp'`; then
    echo shar: \"'tursim/findnext.inp'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/findnext.inp'
  # end of 'tursim/findnext.inp'
fi
if test -f 'tursim/findnext.tur' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/findnext.tur'\"
else
  echo shar: Extracting \"'tursim/findnext.tur'\" \(334 characters\)
  sed "s/^X//" >'tursim/findnext.tur' <<'END_OF_FILE'
XINPUTFILE = findnext.inp
XTAPELENGTH = 40
XMAXSTATES = 4
XINITSTATE = 1
XHALTSTATE = 4
XBLANK = .
X
X;
X; Searches the second occurence of the non-blanco character in the
X; first cell, alphabet is supposed to be x, y, .
X;
X
Xd(1,x)=(2,R)
Xd(1,y)=(3,R)
Xd(1,.)=(4,.)
X
Xd(2,y)=(2,R)
Xd(2,.)=(2,R)
Xd(2,x)=(4,x)
X
Xd(3,x)=(3,R)
Xd(3,.)=(3,R)
Xd(3,y)=(4,y)
END_OF_FILE
  if test 334 -ne `wc -c <'tursim/findnext.tur'`; then
    echo shar: \"'tursim/findnext.tur'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/findnext.tur'
  # end of 'tursim/findnext.tur'
fi
if test -f 'tursim/makefile' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/makefile'\"
else
  echo shar: Extracting \"'tursim/makefile'\" \(301 characters\)
  sed "s/^X//" >'tursim/makefile' <<'END_OF_FILE'
Xtursim.o: tursim.c turing.o      
X	gcc -Wall -o tursim tursim.c turing.o tape.o trans.o
X	tursim not.tur | more
X	tursim findnext.tur | more
X	tursim oddeven.tur | more
X
Xturing.o: turing.c tape.o trans.o
X	gcc -Wall -c turing.c
X
Xtape.o: tape.c
X	gcc -Wall -c tape.c
X
Xtrans.o: trans.c
X	gcc -Wall -c trans.c
END_OF_FILE
  if test 301 -ne `wc -c <'tursim/makefile'`; then
    echo shar: \"'tursim/makefile'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/makefile'
  # end of 'tursim/makefile'
fi
if test -f 'tursim/not.inp' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/not.inp'\"
else
  echo shar: Extracting \"'tursim/not.inp'\" \(27 characters\)
  sed "s/^X//" >'tursim/not.inp' <<'END_OF_FILE'
Xabcdefghijklmnopqrstuvwxyz
END_OF_FILE
  if test 27 -ne `wc -c <'tursim/not.inp'`; then
    echo shar: \"'tursim/not.inp'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/not.inp'
  # end of 'tursim/not.inp'
fi
if test -f 'tursim/not.tur' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/not.tur'\"
else
  echo shar: Extracting \"'tursim/not.tur'\" \(157 characters\)
  sed "s/^X//" >'tursim/not.tur' <<'END_OF_FILE'
XINPUTFILE = not.inp
XTAPELENGTH = 30
XMAXSTATES = 3
XINITSTATE = 1
XHALTSTATE = 2
XBLANK = .
X;
X; Goes right until . and writes 1
X;
Xd(1,~.) = (1,R)
Xd(1,.) = (2,1)
END_OF_FILE
  if test 157 -ne `wc -c <'tursim/not.tur'`; then
    echo shar: \"'tursim/not.tur'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/not.tur'
  # end of 'tursim/not.tur'
fi
if test -f 'tursim/oddeven.inp' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/oddeven.inp'\"
else
  echo shar: Extracting \"'tursim/oddeven.inp'\" \(31 characters\)
  sed "s/^X//" >'tursim/oddeven.inp' <<'END_OF_FILE'
X#111111111111111111111111111#
X
END_OF_FILE
  if test 31 -ne `wc -c <'tursim/oddeven.inp'`; then
    echo shar: \"'tursim/oddeven.inp'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/oddeven.inp'
  # end of 'tursim/oddeven.inp'
fi
if test -f 'tursim/oddeven.tur' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/oddeven.tur'\"
else
  echo shar: Extracting \"'tursim/oddeven.tur'\" \(337 characters\)
  sed "s/^X//" >'tursim/oddeven.tur' <<'END_OF_FILE'
XINPUTFILE = oddeven.inp
XTAPELENGTH = 30
XMAXSTATES = 10
XINITSTATE = 10
XHALTSTATE = 5
XBLANK = .
X;
X;  1 = even # of 1's      0 = odd # of 1's
X;
Xd(10,#) = (1,R)
Xd(1,1) = (9,R)
Xd(1,#) = (2,L)
Xd(2,1) = (3,.)
Xd(2,#) = (4,R)
Xd(3,.) = (2,L)
Xd(4,.) = (5,1)
Xd(6,.) = (5,0)
Xd(7,#) = (6,R)
Xd(7,1) = (8,.)
Xd(8,.) = (7,L)
Xd(9,#) = (7,L)
Xd(9,1) = (1,R)
END_OF_FILE
  if test 337 -ne `wc -c <'tursim/oddeven.tur'`; then
    echo shar: \"'tursim/oddeven.tur'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/oddeven.tur'
  # end of 'tursim/oddeven.tur'
fi
if test -f 'tursim/tape.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/tape.c'\"
else
  echo shar: Extracting \"'tursim/tape.c'\" \(5826 characters\)
  sed "s/^X//" >'tursim/tape.c' <<'END_OF_FILE'
X/* --------------------------------------------------------------------------
X    Description:      Implementation of operations on a "n-tape-system"
X    Target-compiler:  Turbo-C++ V3.0 (ANSI-C)
X    Last update:      9/12/1992
X
X    (C) 1992  Herman Horsten && Sven Boden
X-------------------------------------------------------------------------- */
X
X#include <string.h>
X#include <stdlib.h>
X#include <ctype.h>
X#include "tape.h"
X
X/* ----------------------------------------------------------------------- */
Xint InitTapeSystem(struct TapeSystem *tapeSystem, unsigned int nrOfTapes,
X                                          unsigned int length, char blanco)
X{
X  unsigned int i, nrOfTape;
X
X  if ((nrOfTapes == 0) || (length == 0) || (iscntrl(blanco)))
X    return 0;
X  tapeSystem->tape = (char**)malloc(sizeof(char*) * nrOfTapes);
X  if (tapeSystem->tape == NULL)
X    return 0;
X  tapeSystem->posTapeHead = (unsigned int*)
X                                  malloc(sizeof(unsigned int) * nrOfTapes);
X  if (tapeSystem->posTapeHead == NULL)
X    return 0;
X  for (nrOfTape = 0; nrOfTape < nrOfTapes; nrOfTape++)
X  {
X    tapeSystem->tape[nrOfTape] = (char*)malloc(sizeof(char) * (length + 1));
X    if (tapeSystem->tape[nrOfTape] == NULL)
X      return 0;
X    /*
X        Initialise tape
X    */
X    for (i = 0; i < length; i++)
X      tapeSystem->tape[nrOfTape][i] = blanco;
X    /*
X        Add null-character
X    */
X    tapeSystem->tape[nrOfTape][length] = '\0';
X    tapeSystem->posTapeHead[nrOfTape] = 0;
X  }
X  tapeSystem->nrOfTapes   = nrOfTapes;
X  tapeSystem->blanco      = blanco;
X  tapeSystem->tapeLength  = length;
X
X  return 1;
X}
X/* ----------------------------------------------------------------------- */
Xvoid DisposeTapeSystem(struct TapeSystem *tapeSystem)
X{
X  unsigned int nrOfTape;
X
X  for (nrOfTape = 0; nrOfTape < tapeSystem->nrOfTapes; nrOfTape++)
X    free(tapeSystem->tape[nrOfTape]);
X  free(tapeSystem->tape);
X  free(tapeSystem->posTapeHead);
X}
X/* ----------------------------------------------------------------------- */
Xint TapeHeadReset(struct TapeSystem *tapeSystem, unsigned int nrOfTape)
X{
X  if (nrOfTape < tapeSystem->nrOfTapes)
X    tapeSystem->posTapeHead[nrOfTape] = 0;
X  else
X    return 0;
X
X  return 1;
X}
X/* ----------------------------------------------------------------------- */
Xint TapeHeadLeft(struct TapeSystem *tapeSystem, unsigned int nrOfTape)
X{
X  if ((nrOfTape < tapeSystem->nrOfTapes) &&
X                                (tapeSystem->posTapeHead[nrOfTape] > 0))
X    tapeSystem->posTapeHead[nrOfTape]--;
X  else
X    return 0;
X
X  return 1;
X}
X/* ----------------------------------------------------------------------- */
Xint TapeHeadRight(struct TapeSystem *tapeSystem, unsigned int nrOfTape)
X{
X  if ((nrOfTape < tapeSystem->nrOfTapes) &&
X          (tapeSystem->posTapeHead[nrOfTape] < tapeSystem->tapeLength - 1))
X    tapeSystem->posTapeHead[nrOfTape]++;
X  else
X    return 0;
X
X  return 1;
X}
X/* ----------------------------------------------------------------------- */
Xint WriteSymbol(struct TapeSystem *tapeSystem, unsigned int nrOfTape,
X                                                                char symbol)
X{
X  if ((nrOfTape < tapeSystem->nrOfTapes) && (!iscntrl(symbol)) &&
X              (tapeSystem->posTapeHead[nrOfTape] < tapeSystem->tapeLength))
X    tapeSystem->tape[nrOfTape][tapeSystem->posTapeHead[nrOfTape]] = symbol;
X  else
X    return 0;
X
X  return 1;
X}
X/* ----------------------------------------------------------------------- */
Xint ReadSymbol(const struct TapeSystem *tapeSystem, unsigned int nrOfTape, char *symbol)
X{
X  if ((nrOfTape < tapeSystem->nrOfTapes) &&
X              (tapeSystem->posTapeHead[nrOfTape] < tapeSystem->tapeLength))
X    *symbol = tapeSystem->tape[nrOfTape][tapeSystem->posTapeHead[nrOfTape]];
X  else
X    return 0;
X
X  return 1;
X}
X/* ----------------------------------------------------------------------- */
Xint WriteString(struct TapeSystem *tapeSystem, unsigned int nrOfTape,
X                                                          const char *string)
X{
X  unsigned int i = 0;
X
X  if (nrOfTape < tapeSystem->nrOfTapes)
X  {
X    while ((i < tapeSystem->tapeLength) && (!iscntrl(string[i])))
X    {
X      tapeSystem->tape[nrOfTape][i] = string[i];
X      i++;
X    }
X  }
X  else
X    return 0;
X
X  return 1;
X}
X/* ----------------------------------------------------------------------- */
Xconst char* GetTape(const struct TapeSystem *tapeSystem,
X                                                      unsigned int nrOfTape)
X{
X  if (nrOfTape < tapeSystem->nrOfTapes)
X    return tapeSystem->tape[nrOfTape];
X  else
X    return NULL;
X}
X/* ----------------------------------------------------------------------- */
Xunsigned int GetPosTapeHead(const struct TapeSystem *tapeSystem,
X                                                      unsigned int nrOfTape)
X{
X  if ((nrOfTape < tapeSystem->nrOfTapes) &&
X              (tapeSystem->posTapeHead[nrOfTape] < tapeSystem->tapeLength))
X    return tapeSystem->posTapeHead[nrOfTape];
X  else
X    return 0;
X}
X/* ----------------------------------------------------------------------- */
Xunsigned int GetNrOfTapes(const struct TapeSystem *tapeSystem)
X{
X  return tapeSystem->nrOfTapes;
X}
X/* ----------------------------------------------------------------------- */
Xint ClearTape(struct TapeSystem *tapeSystem, unsigned int nrOfTape)
X{
X  unsigned int i;
X
X  if (nrOfTape < tapeSystem->nrOfTapes)
X  {
X    for (i = 0; i < tapeSystem->tapeLength; i++)
X      tapeSystem->tape[nrOfTape][i] = tapeSystem->blanco;
X    tapeSystem->posTapeHead[nrOfTape] = 0;
X  }
X  else
X    return 0;
X
X  return 1;
X}
X/* ----------------------------------------------------------------------- */
X
X/* --------------------------------------------------------------------------
X    EOF tape.c
X-------------------------------------------------------------------------- */
END_OF_FILE
  if test 5826 -ne `wc -c <'tursim/tape.c'`; then
    echo shar: \"'tursim/tape.c'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/tape.c'
  # end of 'tursim/tape.c'
fi
if test -f 'tursim/tape.h' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/tape.h'\"
else
  echo shar: Extracting \"'tursim/tape.h'\" \(6644 characters\)
  sed "s/^X//" >'tursim/tape.h' <<'END_OF_FILE'
X/* --------------------------------------------------------------------------
X    Description:      Definition of a "n-tape-system" and its operations
X    Target-compiler:  Turbo-C++ V3.0 (ANSI-C)
X    Last update:      9/12/1992
X
X    (C) 1992  Herman Horsten && Sven Boden
X-------------------------------------------------------------------------- */
X
X#ifndef __TAPE_H
X#define __TAPE_H
X
X/* --------------------------------------------------------------------------
X    TYPES
X-------------------------------------------------------------------------- */
X
X/* --------------------------------------------------------------------------
X    Definition of a "n-tape-system" = n x (tape + tape-head)
X-------------------------------------------------------------------------- */
X
Xstruct TapeSystem
X{
X  char          **tape;
X  char          blanco;
X  unsigned int  nrOfTapes;
X  unsigned int  tapeLength;
X  unsigned int  *posTapeHead;
X};
X
X/* --------------------------------------------------------------------------
X    PROTOTYPES
X-------------------------------------------------------------------------- */
X
X/*
X    Purpose:        Initialisation of tape-system
X    Precondition:   Tape-system doesn't exist
X    Postcondition:  Tape-system exists (length of the tapes used by this tape-
X                    system is determined by second parameter), all tapes
X                    are filled with blancos (not a control character),
X                    tapehead of every tape points to first cell
X    Return-value:   0 = error
X                    1 = no error
X*/
Xint InitTapeSystem(struct TapeSystem *tapeSystem, unsigned int nrOfTapes,
X                                        unsigned int length, char blanco);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Disposing the entire tape-system
X    Precondition:   Tape-system exists
X    Postcondition:  Tape-system doesn't exist
X*/
Xvoid DisposeTapeSystem(struct TapeSystem *tapeSystem);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Moving the tapehead to the beginning of the tape
X    Precondition:   Tape-system exists
X    Postcondition:  Tapehead points to the first cell of the tape
X    Return-value:   0 = error
X                    1 = no error
X*/
Xint TapeHeadReset(struct TapeSystem *tapeSystem, unsigned int nrOfTape);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Moving the tapehead one place to the left
X    Precondition:   Tape-system exists and tapehead points to cell n (n > 0)
X    Postcondition:  Tapehead points to cell n-1
X    Return-value:   0 = error
X                    1 = no error
X*/
Xint TapeHeadLeft(struct TapeSystem *tapeSystem, unsigned int nrOfTape);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Moving the tapehead one place to the right
X    Precondition:   Tape-system exists and tapehead points to cell n
X                    (n < length tape)
X    Postcondition:  Tapehead points to cell n+1
X    Return-value:   0 = error
X                    1 = no error
X*/
Xint TapeHeadRight(struct TapeSystem *tapeSystem, unsigned int nrOfTape);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Writing a symbol on the tape at the current position of
X                    the tapehead
X    Precondition:   Tape-system exists, tapehead points to cell n, symbol is
X                    not a control character
X    Postcondition:  Cell n contains the character "symbol"
X    Return-value:   0 = error
X                    1 = no error
X*/
Xint WriteSymbol(struct TapeSystem *tapeSystem, unsigned int nrOfTape,
X                                                              char symbol);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Reading a symbol of the tape at the current position of
X                    the tapehead
X    Precondition:   Tape-system exists, tapehead points to cell n
X    Postcondition:  The parameter "symbol" contains the character at cell n
X    Return-value:   0 = error
X                    1 = no error
X*/
Xint ReadSymbol(const struct TapeSystem *tapeSystem, unsigned int nrOfTape,
X                                                              char *symbol);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Writing an entire string on tape starting at first cell,
X    Precondition:   Tape-system exist
X    Postcondition:  Tape of tape-system contains a duplicate of the string
X    Return-value:   0 = error
X                    1 = no error
X*/
Xint WriteString(struct TapeSystem *tapeSystem, unsigned int nrOfTape,
X                                                        const char *string);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Returns 1 tape of tape-system
X    Precondition:   TapeSystem exists
X    Postcondition:  Nothing changes
X    Return-value:   Pointer to the tape, if tape exists
X                    NULL, if tape doesn't exist
X*/
Xconst char* GetTape(const struct TapeSystem *tapeSystem,
X                                                    unsigned int nrOfTape);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Returns position of tapehead
X    Precondition:   TapeSystem exists
X    Postcondition:  Nothing changes
X    Return-value:   Current position of tapehead
X*/
Xunsigned int GetPosTapeHead(const struct TapeSystem *tapeSystem,
X                                                      unsigned int nrOfTape);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Returns the number of tapes in tapeSystem
X    Precondition:   tapeSystem exists
X    Postcondition:  Nothing changes
X    Return-value:   Number of tapes
X*/
Xunsigned int GetNrOfTapes(const struct TapeSystem *tapeSystem);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Wipes 1 tape
X    Precondition:   TapeSystem exists
X    Postcondition:  TapeSystem with empty tape, tape-head points to first
X                    element
X    Return-value:   0 = error
X                    1 = no error
X*/
Xint ClearTape(struct TapeSystem *tapeSystem, unsigned int nrOfTape);
X/* ----------------------------------------------------------------------- */
X
X#endif
X
X/* --------------------------------------------------------------------------
X    EOF tape.h
X-------------------------------------------------------------------------- */
END_OF_FILE
  if test 6644 -ne `wc -c <'tursim/tape.h'`; then
    echo shar: \"'tursim/tape.h'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/tape.h'
  # end of 'tursim/tape.h'
fi
if test -f 'tursim/trans.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/trans.c'\"
else
  echo shar: Extracting \"'tursim/trans.c'\" \(4336 characters\)
  sed "s/^X//" >'tursim/trans.c' <<'END_OF_FILE'
X/* --------------------------------------------------------------------------
X    Description:      Implementation of operations on transition-matrix
X    Target-compiler:  Turbo-C++ V3.0 (ANSI-C)
X    Last update:      26/11/1992
X
X    (C) 1992  Herman Horsten && Sven Boden
X-------------------------------------------------------------------------- */
X
X#include <limits.h>
X#include <stdlib.h>
X#include <ctype.h>
X#include "trans.h"
X
X/* ----------------------------------------------------------------------- */
Xchar GetIndex(char symbol)
X{
X  return symbol - ' ';
X}
X/* ----------------------------------------------------------------------- */
X/*
X    Initializes TransitionMatrix
X
X    TransitionMatrix is a 2-dimensional array of Transitions:
X
X      + symbols
X      s . . . . . . .
X      t . . . . . . .
X      a . . . . . . .
X      t . . . . . . .
X      e . . . . . . .
X      s . . . . . . .
X
X*/
Xint InitMatrix(struct TransitionMatrix *transMatrix, unsigned int maxStates)
X{
X  char symbol;
X  unsigned int state;
X
X  if (maxStates < 2)
X    return 0;
X  /*
X      Create a two-dimensional array
X  */
X  transMatrix->matrix = (struct Transition**)
X                  malloc(sizeof(struct Transition*) * (GetIndex(CHAR_MAX)));
X  if (transMatrix->matrix == NULL)
X    return 0;
X  for (symbol = ' '; symbol < CHAR_MAX; symbol++)
X  {
X    /*
X      add one extra state which serves as a "null-state"
X    */
X    transMatrix->matrix[GetIndex(symbol)] = (struct Transition*)
X                        malloc(sizeof(struct Transition) * (maxStates + 1));
X    if (transMatrix->matrix[GetIndex(symbol)] == NULL)
X      return 0;
X  }
X  /*
X      Initialize matrix
X  */
X  for (symbol = ' '; symbol < CHAR_MAX; symbol++)
X    for (state = 0; state < maxStates + 1; state++)
X    {
X      transMatrix->matrix[GetIndex(symbol)][state].newState   = NULL_STATE;
X      transMatrix->matrix[GetIndex(symbol)][state].newSymbol  = '\0';
X    }
X  transMatrix->nrOfStates   = maxStates + 1;
X  transMatrix->nrOfSymbols  = GetIndex(CHAR_MAX);
X
X  return 1;
X}
X/* ----------------------------------------------------------------------- */
Xvoid DisposeMatrix(struct TransitionMatrix *transMatrix)
X{
X  char symbol;
X
X  for (symbol = ' '; symbol < CHAR_MAX; symbol++)
X    free(transMatrix->matrix[GetIndex(symbol)]);
X  free(transMatrix->matrix);
X}
X/* ----------------------------------------------------------------------- */
Xint SetTransition(struct TransitionMatrix *transMatrix,
X                   unsigned int state, char symbol,
X                   unsigned int newState, char newSymbol,
X                   int *changed)
X{
X  *changed = 0;
X  /*
X      There may be no transitions from the null-state to another state !
X  */
X  if ((state == NULL_STATE) || (state >= transMatrix->nrOfStates))
X    return 0;
X  if (newState >= transMatrix->nrOfStates)
X    return 0;
X  if ((iscntrl(symbol)) || (iscntrl(newSymbol)))
X    return 0;
X  if ((transMatrix->matrix[GetIndex(symbol)][state].newState != NULL_STATE) &&
X      (transMatrix->matrix[GetIndex(symbol)][state].newState != newState) &&
X      (transMatrix->matrix[GetIndex(symbol)][state].newSymbol != newSymbol))
X    *changed = 1; 
X  transMatrix->matrix[GetIndex(symbol)][state].newState       = newState;
X  transMatrix->matrix[GetIndex(symbol)][state].newSymbol      = newSymbol;
X
X  return 1;
X}
X/* ----------------------------------------------------------------------- */
Xint GetTransition(const struct TransitionMatrix *transMatrix,
X                          unsigned int state, char symbol,
X                          struct Transition *transition)
X{
X  if ((state == NULL_STATE) || (state >= transMatrix->nrOfStates))
X    return 0;
X  if (iscntrl(symbol))
X    return 0;
X  *transition = transMatrix->matrix[GetIndex(symbol)][state];
X
X  return 1;
X}
X/* ----------------------------------------------------------------------- */
Xunsigned int GetNewState(const struct Transition *transition)
X{
X  return transition->newState;
X}
X/* ----------------------------------------------------------------------- */
Xchar GetNewSymbol(const struct Transition *transition)
X{
X  return transition->newSymbol;
X}
X/* ----------------------------------------------------------------------- */
X
X/* --------------------------------------------------------------------------
X    EOF trans.c
X-------------------------------------------------------------------------- */
END_OF_FILE
  if test 4336 -ne `wc -c <'tursim/trans.c'`; then
    echo shar: \"'tursim/trans.c'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/trans.c'
  # end of 'tursim/trans.c'
fi
if test -f 'tursim/trans.h' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/trans.h'\"
else
  echo shar: Extracting \"'tursim/trans.h'\" \(4410 characters\)
  sed "s/^X//" >'tursim/trans.h' <<'END_OF_FILE'
X/* --------------------------------------------------------------------------
X    Description:      Definition of a transition-matrix
X    Target-compiler:  Turbo-C++ V3.0 (ANSI-C)
X    Last update:      20/11/1992
X
X    (C) 1992  Herman Horsten && Sven Boden
X-------------------------------------------------------------------------- */
X
X#ifndef __TRANS_H
X#define __TRANS_H
X
X/*
X    When there's no transition from one state to another (given a current
X    symbol), there exist a transition to the "null-state"
X*/
X
X#define NULL_STATE 0
X
X/* --------------------------------------------------------------------------
X    TYPES
X-------------------------------------------------------------------------- */
X
X/* --------------------------------------------------------------------------
X    Definition of a transition
X-------------------------------------------------------------------------- */
X
Xstruct Transition
X{
X  unsigned int  newState;
X  char          newSymbol;
X};
X
X/* --------------------------------------------------------------------------
X    Definition of a transition-matrix
X-------------------------------------------------------------------------- */
X
Xstruct TransitionMatrix
X{
X  struct Transition **matrix;
X  unsigned int      nrOfStates;
X  unsigned int      nrOfSymbols;
X};
X
X/* --------------------------------------------------------------------------
X    PROTOTYPES
X-------------------------------------------------------------------------- */
X
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Initializes a transition-matrix
X    Precondition:   Transition-matrix doesn't exist
X    Postcondition:  Transition-matrix exists
X    Return-value:   0 = error
X                    1 = no error
X*/
Xint InitMatrix(struct TransitionMatrix *matrix, unsigned int maxStates);
X
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Disposes a transition-matrix
X    Precondition:   Matrix exists
X    Postcondition:  Matrix doesn't exist
X*/
Xvoid DisposeMatrix(struct TransitionMatrix *matrix);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Adds a new transition to the matrix
X    Precondition:   Matrix exists, legal values for state are 1 to
X                    maxStates, legal values for newState are 0 to maxStates,
X                    value 0 for newState means that there is no transition,
X                    symbol and newSymbol may not be a control character,
X                    changed = 1 if a transition has changed, else changed = 0
X    Postcondition:  Matrix + new transition
X    Return-value:   0 = error
X                    1 = no error
X*/
Xint SetTransition(struct TransitionMatrix *transMatrix,
X                          unsigned int state, char symbol,
X                          unsigned int newState, char newSymbol,
X                          int *changed);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Returns a transition given a certain state and symbol
X    Precondition:   Matrix exists, legal values for state are 1 to maxStates,
X                    symbol is not a control-character
X    Postcondition:  No changes in matrix, only the appropriate transition
X                    is returned
X    Return-value:   0 = error
X                    1 = no error
X*/
Xint GetTransition(const struct TransitionMatrix *transMatrix,
X                          unsigned int state, char symbol,
X                          struct Transition *transition);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Returns the new state
X    Precondition:   Transition exists
X    Postcondition:  Nothing changes
X    Return-value:   Number of a state
X*/
Xunsigned int GetNewState(const struct Transition *transition);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Returns the new symbol
X    Precondition:   Transition exists
X    Postcondition:  Nothing changes
X    Return-value:   Symbol
X*/
Xchar GetNewSymbol(const struct Transition *transition);
X/* ----------------------------------------------------------------------- */
X
X#endif
X
X/* --------------------------------------------------------------------------
X    EOF trans.h
X-------------------------------------------------------------------------- */
END_OF_FILE
  if test 4410 -ne `wc -c <'tursim/trans.h'`; then
    echo shar: \"'tursim/trans.h'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/trans.h'
  # end of 'tursim/trans.h'
fi
if test -f 'tursim/turing.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/turing.c'\"
else
  echo shar: Extracting \"'tursim/turing.c'\" \(5725 characters\)
  sed "s/^X//" >'tursim/turing.c' <<'END_OF_FILE'
X/* --------------------------------------------------------------------------
X    Description:      Implementation of operations on a Turing-Machine
X    Target-compiler:  Turbo-C++ V3.0 (ANSI-C)
X    Last update:      15/12/1992
X
X    (C) 1992  Herman Horsten && Sven Boden
X-------------------------------------------------------------------------- */
X
X#include <ctype.h>
X#include "turing.h"
X
X/* ----------------------------------------------------------------------- */
Xint IsAction(char symbol)
X{
X  if ((symbol == 'R') || (symbol == 'L'))
X    return 1;
X  else
X    return 0;
X}
X/* ----------------------------------------------------------------------- */
Xenum Error InitTM(struct TuringMachine *turingMachine,
X                                                unsigned int maxStates,
X                                                unsigned int lengthTape,
X                                                unsigned int initState,
X                                                unsigned int haltState,
X                                                char blanco)
X{
X  if ((initState == NULL_STATE) || (haltState == NULL_STATE) ||
X      (initState == haltState)  || (initState > maxStates)   ||
X      (haltState > maxStates))
X    return IllegalState;
X  if ((iscntrl(blanco)) || (IsAction(blanco)))
X    return IllegalSymbol;
X  if (!InitMatrix(&turingMachine->transMatrix, maxStates))
X    return Error;
X  if (!InitTapeSystem(&turingMachine->tapeSystem, 1, lengthTape, blanco))
X    return Error;
X  turingMachine->state        = initState;
X  turingMachine->initialState = initState;
X  turingMachine->haltState    = haltState;
X  turingMachine->cycles       = 0;
X
X  return NoError;
X}
X/* ----------------------------------------------------------------------- */
Xvoid DisposeTM(struct TuringMachine *turingMachine)
X{
X  DisposeMatrix(&turingMachine->transMatrix);
X  DisposeTapeSystem(&turingMachine->tapeSystem);
X}
X/* ----------------------------------------------------------------------- */
Xenum Error AddTransFunctionTM(struct TuringMachine *turingMachine,
X                                  unsigned int state, char symbol,
X                                  unsigned int newState, char newSymbol,
X                                  int *changed)
X{
X  if ((state != turingMachine->haltState) && (!IsAction(symbol)) &&
X            SetTransition(&turingMachine->transMatrix, state, symbol,
X                                                       newState, newSymbol,
X                                                       changed))
X    return NoError;
X  else
X    return Error;
X}
X/* ----------------------------------------------------------------------- */
Xenum Error SetTapeTM(struct TuringMachine *turingMachine, const char *string)
X{
X  unsigned int i = 0;
X
X  while (string[i] != '\0')
X  {
X    if (IsAction(string[i]))
X      return IllegalSymbol;
X    i++;
X  }
X  if (!WriteString(&turingMachine->tapeSystem, 0, string))
X    return IllegalSymbol;
X
X  return NoError;
X}
X/* ----------------------------------------------------------------------- */
Xconst char* GetTapeTM(const struct TuringMachine *turingMachine)
X{
X  return GetTape(&turingMachine->tapeSystem, 0);
X}
X/* ----------------------------------------------------------------------- */
Xunsigned int GetStateTM(const struct TuringMachine *turingMachine)
X{
X  return turingMachine->state;
X}
X/* ----------------------------------------------------------------------- */
Xunsigned int GetPosTapeHeadTM(const struct TuringMachine *turingMachine)
X{
X  return GetPosTapeHead(&turingMachine->tapeSystem, 0);
X}
X/* ----------------------------------------------------------------------- */
Xunsigned int GetPerformedTransTM(const struct TuringMachine *turingMachine)
X{
X  return turingMachine->cycles;
X}
X/* ----------------------------------------------------------------------- */
Xenum Error TraceTM(struct TuringMachine *turingMachine)
X{
X  struct Transition transition;
X  char symbol, newSymbol;
X
X  ReadSymbol(&turingMachine->tapeSystem, 0, &symbol);
X  if (!GetTransition(&turingMachine->transMatrix, turingMachine->state,
X                                                  symbol, &transition))
X    return Error;
X  /*
X      Is there a transition ?
X  */
X  if (GetNewState(&transition) == NULL_STATE)
X    return NormalTerminationNotInHaltState;
X  turingMachine->cycles++;
X  newSymbol = GetNewSymbol(&transition);
X  /*
X      Move tapehead or write a symbol
X  */
X  switch (newSymbol)
X  {
X    case 'L':
X      if (!TapeHeadLeft(&turingMachine->tapeSystem, 0))
X        return AbnormalTermination;
X      break;
X    case 'R':
X      if (!TapeHeadRight(&turingMachine->tapeSystem, 0))
X        return TapeTooSmall;
X      break;
X    default:
X      if (!WriteSymbol(&turingMachine->tapeSystem, 0, newSymbol))
X        return IllegalSymbol;
X  }
X  /*
X      Jump to new state
X  */
X  turingMachine->state = GetNewState(&transition);
X  if (turingMachine->state == turingMachine->haltState)
X    return NormalTerminationInHaltState;
X
X  return Running;
X}
X/* ----------------------------------------------------------------------- */
Xenum Error RunTM(struct TuringMachine *turingMachine)
X{
X  enum Error status;
X
X  do
X  {
X    status = TraceTM(turingMachine);
X  }
X  while (status == Running);
X
X  return status;
X}
X/* ----------------------------------------------------------------------- */
Xvoid ResetTM(struct TuringMachine *turingMachine)
X{
X  turingMachine->state  = turingMachine->initialState;
X  turingMachine->cycles = 0;
X  ClearTape(&turingMachine->tapeSystem, 0);
X}
X/* ----------------------------------------------------------------------- */
X
X/* --------------------------------------------------------------------------
X    EOF turing.c
X-------------------------------------------------------------------------- */
END_OF_FILE
  if test 5725 -ne `wc -c <'tursim/turing.c'`; then
    echo shar: \"'tursim/turing.c'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/turing.c'
  # end of 'tursim/turing.c'
fi
if test -f 'tursim/turing.h' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/turing.h'\"
else
  echo shar: Extracting \"'tursim/turing.h'\" \(7422 characters\)
  sed "s/^X//" >'tursim/turing.h' <<'END_OF_FILE'
X/* --------------------------------------------------------------------------
X    Description:      Definition of a Turing-machine
X    Target-compiler:  Turbo-C++ V3.0 (ANSI-C)
X    Last update:      15/12/1992
X
X    (C) 1992  Herman Horsten && Sven Boden
X-------------------------------------------------------------------------- */
X
X#ifndef __TURING_H
X#define __TURING_H
X
X#include "trans.h"
X#include "tape.h"
X
X/* --------------------------------------------------------------------------
X    TYPES
X-------------------------------------------------------------------------- */
X
X/* --------------------------------------------------------------------------
X    Error-codes
X-------------------------------------------------------------------------- */
X
Xenum Error {  NoError,
X              Error,
X              IllegalState,
X              IllegalSymbol,
X              AbnormalTermination,
X              NormalTerminationNotInHaltState,
X              NormalTerminationInHaltState,
X              TapeTooSmall,
X              Running
X            };
X
X/* --------------------------------------------------------------------------
X    Definition of a Turing-Machine
X-------------------------------------------------------------------------- */
X
Xstruct TuringMachine
X{
X  struct TapeSystem         tapeSystem;
X  struct TransitionMatrix   transMatrix;
X  unsigned int              state;          /* current state            */
X  unsigned int              initialState;
X  unsigned int              haltState;
X  unsigned int              cycles;         /* # performed transitions  */
X};
X
X/* --------------------------------------------------------------------------
X    PROTOTYPES
X--------------------------------------------------------------------------  */
X/*
X    Purpose:        Initializes a Turing-Machine
X                    alphabet = ASCII characters \ {L,R}
X                                                \ control characters
X                                                \ blanco
X                    tape-symbols = alphabet U {blanco}
X    Precondition:   Turing-Machine doesn't exist, maxStates > 1,
X                    lengthTape > 0, initState > 0, haltState > 0,
X                    initState <= maxStates, haltState <= maxStates,
X                    initState != haltState, blanco is not element of {L,R}
X    Postcondition:  Turing-Machine exists
X    Return-value:   Error-code
X*/
Xenum Error InitTM(struct TuringMachine *turingMachine,
X                                                unsigned int maxStates,
X                                                unsigned int lengthTape,
X                                                unsigned int initState,
X                                                unsigned int haltState,
X                                                char blanco);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Disposes a Turing-Machine
X    Precondition:   Turing-Machine exists
X    Postcondition:  Turing-Machine doesn't exist
X*/
Xvoid DisposeTM(struct TuringMachine *turingMachine);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Adding a transition-function to the Turing-Machine
X    Precondition:   Turing-Machine exists, legal values for a state are
X                    numbers from 1 to maxStates and state is not the halt-
X                    state, legal values for newState are numbers from 0 to
X                    maxStates, value 0 means that there is no transition,
X                    symbol is an element of the tape-symbols and newSymbol is
X                    an element of the tape-symbols U {L,R}, changed = 1 if a
X                    transition has changed, else changed = 0
X    Postcondition:  Turing-Machine + new transition-function
X    Return-value:   Error-code
X*/
Xenum Error AddTransFunctionTM(struct TuringMachine *turingMachine,
X                                 unsigned int state, char symbol,
X                                 unsigned int newState, char newSymbol,
X                                 int *changed);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Initializes the tape of the Turing-Machine
X    Precondition:   Turing-Machine exists, string consists of legal symbols
X                    (ASCII-characters \ {L,R} \ control characters)
X    Postcondition:  A string of symbols is written on the tape
X    Return-value:   Error-code
X*/
Xenum Error SetTapeTM(struct TuringMachine *turingMachine, const char *string);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Returns the tape of the Turing-Machine
X    Precondition:   Turing-Machine exists
X    Postcondition:  Nothing changes
X    Return-value:   Pointer to the tape
X*/
Xconst char* GetTapeTM(const struct TuringMachine *turingMachine);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Returns the current state of the Turing-Machine
X    Precondition:   Turing-Machine exists
X    Postcondition:  Nothing changes
X    Return-value:   Number of the current state
X*/
Xunsigned int GetStateTM(const struct TuringMachine *turingMachine);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Returns the current position of the tapehead
X    Precondition:   Turing-Machine exists
X    Postcondition:  Nothing changes,
X    Return-value:   The position of the tapehead
X*/
Xunsigned int GetPosTapeHeadTM(const struct TuringMachine *turingMachine);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Returns the number of transitions performed by the TM
X    Precondition:   Turing-Machine exists
X    Postcondition:  Nothing changes
X    Return-value:   Number of performed transitions
X*/
Xunsigned int GetPerformedTransTM(const struct TuringMachine *turingMachine);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Performs one transition
X    Precondition:   Turing-Machine exists
X    Postcondition:  Turing-Machine in a new state depending on the current
X                    symbol and state,
X    Return-value:   The current status of the Turing-Machine
X*/
Xenum Error TraceTM(struct TuringMachine *turingMachine);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Running a Turing-Machine till a normal or abnormal
X                    termination occures
X    Precondition:   Turing-Machine exists
X    Postcondition:  Turing-Machine in halt-state when a normal termination
X                    occures, otherwise the state is undefined,
X    Return-value:   The current status of the Turing-Machine
X*/
Xenum Error RunTM(struct TuringMachine *turingMachine);
X/* ----------------------------------------------------------------------- */
X/*
X    Purpose:        Resetting Turing-Machine
X    Precondition:   Turing-Machine exists
X    Postcondition:  Turing-Machine in initial-state, tapehead to first
X                    position of tape, tape wiped
X*/
Xvoid ResetTM(struct TuringMachine *turingMachine);
X/* ----------------------------------------------------------------------- */
X
X#endif
X
X/* --------------------------------------------------------------------------
X  EOF turing.h
X-------------------------------------------------------------------------- */
END_OF_FILE
  if test 7422 -ne `wc -c <'tursim/turing.h'`; then
    echo shar: \"'tursim/turing.h'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/turing.h'
  # end of 'tursim/turing.h'
fi
if test -f 'tursim/tursim.c' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/tursim.c'\"
else
  echo shar: Extracting \"'tursim/tursim.c'\" \(13741 characters\)
  sed "s/^X//" >'tursim/tursim.c' <<'END_OF_FILE'
X/* --------------------------------------------------------------------------
X     Description:      Turing-Machine Simulator
X     Target-compiler:  Turbo-C++ V3.0 (ANSI-C)
X     Last update:      16/12/1992
X
X     (C) 1992  Sven Boden && Herman Horsten
X--------------------------------------------------------------------------- */
X
X#include <ctype.h>
X#include <stdio.h>
X#include <stdlib.h>
X#include <string.h>
X#include <limits.h>
X#include "turing.h"
X
X#define NOLINENR 0
X
Xchar* ErrorMesg[18] = { NULL,
X                        "syntax error",
X                        "while inserting transition",
X                        "transition already in use",
X                        "inputstring too long for tape",
X                        "inputstring contains illegal characters",
X                        "cannot read input-file",
X                        "during initialisation of Turing-Machine",
X                        "tape too big to fit in memory",
X                        "state out of bound",
X                        "premature end of file",
X                        "can't use ~& as symbol",
X                        "can't use ~ as a sole symbol",
X                        "can't use & as a 'write' symbol",
X                        "can't read transition-file",
X                        "wrong construction of header",
X                        "unknown error",
X                        "syntax error in parameters"
X                       };
X
X
X
Xvoid Errors(unsigned error, unsigned curLine);
X
X/* Function to centralize the output of error-messages,
X   error is the number of the message in the array ErrorMesg that
X   you want to print. If curLine equals NOLINENR the message is printed
X   as is, else the suffix " in line ??" is added where ?? is curLine.
X*/
X
Xvoid DeleteSpaces(char* string);
X/* Function to delete all spaces from a string, this makes it e.g.
X   easier for parsing functions to operate on the string.
X*/
X
Xvoid ReadHeader(FILE* file, char* inputFileName, unsigned int* maxTapeLength,
X                unsigned int* maxStates, unsigned int* haltState,
X                unsigned int* initialState, char* blanco,
X                unsigned* currentLine);
X/* Function to read the header that is needed in every transition-file
X*/
X
Xvoid ReadTransitions(FILE *file, struct TuringMachine *turingMachine,
X                     unsigned int maxStates, unsigned* curLine);
X/* Function that reads the transitions from a file and adds them to
X   the turing-machine
X*/
X
Xenum Error RunTuringMachine(struct TuringMachine *turingMachine,
X                            unsigned int maxTapeLength);
X/* Lets the turing-machine run, and directs the output to the standard
X   output.
X*/
X
Xvoid ReadStringAndPutOnTape(FILE* inputFileName,
X                            struct TuringMachine *turingMachine,
X                            unsigned int maxLengthTape);
X
X/* Reads the characters of the given file until a whitespace is
X   encountered, & and ~ are checked, tape too short,...
X*/
X
X
Xint main(int argc, char **argv)
X{
X   FILE                  *transFile, *inputFile;
X   char                  inputFileName[80], blanco;
X   unsigned int          maxTapeLength, maxStates, haltState, initialState,
X                         curLine = 0;
X   enum Error            status;        /* status of TM after termination */
X   struct TuringMachine  turingMachine;
X
X
X   if (argc < 2)
X   {
X     fprintf(stderr, "\nSYNTAX: TURSIM <TransitionFile>\n");
X     exit(0);
X   }
X   /* File opened ? */
X   if ((transFile = fopen(argv[1], "rt"))== NULL)
X     Errors(14, NOLINENR);
X   /* Read header */
X   ReadHeader(transFile, inputFileName, &maxTapeLength, &maxStates,
X              &haltState, &initialState, &blanco, &curLine);
X   /* Init Turing-Machine */
X   if (InitTM(&turingMachine, maxStates,
X                              maxTapeLength,
X                              initialState,
X                              haltState,
X                              blanco) != NoError)
X     Errors(7, NOLINENR);  /* Error initializing */
X
X   /* Read transitions and put them in the turingmachine */
X   ReadTransitions(transFile, &turingMachine, maxStates, &curLine);
X   fclose(transFile);
X   /* Read input string */
X   if ((inputFile = fopen(inputFileName,"rt")) == NULL)
X     Errors(6, NOLINENR);
X   ReadStringAndPutOnTape(inputFile, &turingMachine, maxTapeLength);
X   fclose(inputFile);
X   /* Run Turing-Machine */
X   status = RunTuringMachine(&turingMachine, maxTapeLength);
X   /* Terminate Turing-Machine */
X   switch (status)
X   {
X     case AbnormalTermination:
X       printf("\nAbnormal termination\n");  /* tapehead falls of left */
X       break;
X     case NormalTerminationInHaltState:
X       printf("\nNormal termination in halt state\n"); /* TM halts */
X       break;
X     case NormalTerminationNotInHaltState:
X       printf("\nTermination not in halt state\n"); /* missing transition */
X       break;
X     default:
X       printf("\nSimulation Error\n"); /* 'fall off' right end */
X   }
X   DisposeTM(&turingMachine);
X
X   return 1;
X}
X
X/* ------------------------------------------------------------------------*/
X
Xvoid Errors(unsigned error, unsigned curLine)
X{
X   fprintf(stderr, "\nError : ");
X   fprintf(stderr, ErrorMesg[error]);
X   if (curLine == NOLINENR)               /* no line specified */
X     fprintf(stderr, "\n");
X   else
X     fprintf(stderr, " in line %u\n", curLine);
X   exit(0);
X}
X
X/* ------------------------------------------------------------------------*/
X
Xvoid DeleteSpaces(char* string)
X{
X   int nextempty = 0, nextfull = 0;
X   int length;
X
X   length = strlen(string);
X   if (strcmp(string, "") == 0)  /* check if empty */
X      return;
X   while (string[nextempty] != ' ')
X     nextempty++;
X   nextfull = nextempty;
X   while (string[nextfull] == ' ')
X     nextfull++;
X   while (nextfull < length-1)
X   {
X      while (string[nextempty] != ' ')
X        nextempty++;
X      while (string[nextfull] == ' ')
X        nextfull++;
X      string[nextempty] = string[nextfull];
X      string[nextfull] = ' ';
X   }
X   string[nextempty+1]='\0';
X}
X
X/* ------------------------------------------------------------------------*/
X
Xvoid ReadHeader(FILE* file, char* inputFileName, unsigned int* maxTapeLength,
X                unsigned int* maxStates, unsigned int* haltState,
X                unsigned int* initialState, char* blanco,
X                unsigned* currentLine)
X{
X   char line[81], string[1];
X
X   (*currentLine)++;
X
X   if (fgets(line, 80, file))
X   {
X    if (sscanf(line, "INPUTFILE = %s", inputFileName) != 1)
X      Errors(15, *currentLine);
X   }
X   else
X     Errors(10, *currentLine);
X   (*currentLine)++;
X   if (fgets(line, 80, file))
X   {
X     if (sscanf(line, "TAPELENGTH = %u", maxTapeLength) != 1)
X       Errors(15, *currentLine);
X   }
X   else
X     Errors(10, *currentLine);
X   (*currentLine)++;
X   if (fgets(line, 80, file) != NULL)
X   {
X     if (sscanf(line, "MAXSTATES = %u", maxStates) != 1)
X       Errors(15, *currentLine);
X   }
X   else
X     Errors(10, *currentLine);
X   (*currentLine)++;
X   if (fgets(line, 80, file) != NULL)
X   {
X     if (sscanf(line, "INITSTATE = %u", initialState) != 1)
X       Errors(15, *currentLine);
X     if (*initialState == 0 || *initialState > *maxStates)
X       Errors(9, *currentLine);  /* state out of bound */
X   }
X   else
X       Errors(10, *currentLine);
X   (*currentLine)++;
X   if (fgets(line, 80, file) != NULL)
X   {
X     if (sscanf(line, "HALTSTATE = %u", haltState) != 1)
X       Errors(15, *currentLine);
X     if (*haltState == 0 || *haltState > *maxStates)
X       Errors(9, *currentLine);  /* state out of bound */
X   }
X   else
X       Errors(10, *currentLine);
X   (*currentLine)++;
X   if (fgets(line, 80, file) != NULL)
X   {
X     if (sscanf(line, "BLANK = %s", string) != 1)  /* to skip whitespaces */
X       Errors(15, *currentLine);
X     *blanco = string[0];
X   }
X   else
X     Errors(10, *currentLine);
X}
X
X/* ------------------------------------------------------------------------*/
X
X
Xvoid ReadTransitions(FILE *file, struct TuringMachine *turingMachine,
X                     unsigned int maxStates, unsigned* curLine)
X{
X   char                  symbol, newSymbol, line[81], dummy, k;
X   unsigned int          state, newState;
X   int                   symbolsRead, changed;
X
X   while (fgets(line, 80, file) != NULL)
X   {
X     (*curLine)++;
X     /* Comment ? */
X     if (line[0] == ';' || strcmp(line, "\n") == 0)
X       continue;
X     /* Delete spaces, easier to parse */
X     DeleteSpaces(line);
X     /* Parse line */
X     symbolsRead = sscanf(line, "d(%u,%c)=(%u,%c)",
X                           &state, &symbol, &newState, &newSymbol);
X     /* Line wasn't read correctly */
X     if (symbolsRead == 2 && symbol == '~')
X     {
X       symbolsRead = sscanf(line, "d(%u,%c%c) = (%u,%c)",
X                            &state, &dummy, &symbol,
X                            &newState, &newSymbol);
X       if (symbol == '&' || newSymbol == '&')  /* ~& doesn't make sense */
X         Errors(11, *curLine);
X       for (k=' '; k<CHAR_MAX; k++)  /* add ~x */
X       {
X         if (k != symbol)            /* leave this transition open */
X         {
X           if (!iscntrl(k) && k != 'R' && k != 'L') /* discard invalid char */
X           {
X             if (AddTransFunctionTM(turingMachine, state, k, newState,
X                                    newSymbol, &changed) != NoError)
X             Errors(2, *curLine);       /* general error */
X             if (changed == 1)          /* impossible to overwrite transition */
X               Errors(3, *curLine);
X           }
X         }
X       }
X     }
X     else if (symbolsRead == 4)
X     {
X       if (symbol == '~' || newSymbol == '~')  /* invalid use of ~ */
X         Errors(12, *curLine);
X       if (newSymbol == '&')                   /* can't write & on tape */
X         Errors(13, *curLine);
X       if (symbol == '&')
X       {
X         for (k=' '; k<CHAR_MAX; k++)  /* add for all x (& as symbol) */
X         {
X           if (!iscntrl(k) && k != 'L' && k!= 'R')  /* discard invalid char */
X           {
X              if (AddTransFunctionTM(turingMachine, state, k, newState,
X                                      newSymbol, &changed) != NoError)
X                Errors(2, *curLine);   /* general error */
X              if (changed == 1)        /* impossible to overwrite transition */
X                Errors(3, *curLine);
X           }
X         }
X       }
X       else
X       {
X         if (state != 0 && state <= maxStates &&
X             newState != 0 && newState <= maxStates) /* states within bounds? */
X         {
X           if (AddTransFunctionTM(turingMachine, state, symbol, newState,
X                                  newSymbol, &changed) != NoError)
X             Errors(2, *curLine);
X           if (changed == 1)
X             Errors(3, *curLine);
X         }
X         else
X           Errors(9, *curLine);          /* state out of bound */
X       }
X     }
X     else
X       Errors(17, *curLine);
X   }
X}
X
X/* ------------------------------------------------------------------------*/
X
Xenum Error RunTuringMachine(struct TuringMachine *turingMachine,
X                            unsigned int maxTapeLength)
X{
X   char                  *tapeHeadString;
X   unsigned int          i, oldPos;
X   enum Error            status;        /* status of TM after termination */
X
X   tapeHeadString = (char*)malloc(sizeof(char) * (maxTapeLength+1));
X   if (tapeHeadString == NULL)
X     Errors(8, NOLINENR);
X   for (i = 0; i < maxTapeLength; i++)
X     tapeHeadString[i] = ' ';
X   tapeHeadString[maxTapeLength] = '\0';
X   printf("\n");
X   tapeHeadString[GetPosTapeHeadTM(turingMachine)] = '^';  /* set 'pointer' */
X   printf("%s\n", GetTapeTM(turingMachine));
X   printf("%s\n",tapeHeadString);
X   printf("state %u        cycle %u\n", GetStateTM(turingMachine),
X                GetPerformedTransTM(turingMachine));
X   oldPos = GetPosTapeHeadTM(turingMachine);
X   do
X   {
X     status = TraceTM(turingMachine);
X     tapeHeadString[oldPos] = ' ';
X     tapeHeadString[GetPosTapeHeadTM(turingMachine)] = '^';
X     printf("%s\n", GetTapeTM(turingMachine));
X     printf("%s\n",tapeHeadString);
X     printf("state %u        cycle %u\n", GetStateTM(turingMachine),
X                                                     GetPerformedTransTM(turingMachine));
X     oldPos = GetPosTapeHeadTM(turingMachine);
X   }
X   while (status == Running);
X   free(tapeHeadString);
X   return status;
X}
X
X/* ------------------------------------------------------------------------*/
X
Xvoid ReadStringAndPutOnTape(FILE* inputFile,
X                             struct TuringMachine *turingMachine,
X                             unsigned int maxLengthTape)
X{
X   char* inputString, ch;
X   int i, count = 0;
X
X   inputString = (char*)malloc(sizeof(char)*(maxLengthTape+1));
X   if (inputString == NULL)
X     Errors(8, NOLINENR);   /* no place for temp tape storage */
X   for (i = 0; i < maxLengthTape; i++)
X     inputString[i] = ' ';  /* clear before use */
X   while ((ch=getc(inputFile))!=EOF && ch != '&' && ch != '~' &&
X           !iscntrl(ch) && ch != ' ' && count++ < maxLengthTape)
X   {
X     inputString[count-1] = ch;
X   }
X   if (count > maxLengthTape)
X     Errors(4, NOLINENR);                   /* Tape too small */
X   if (ch == '~' || ch == '&')
X     Errors(5, NOLINENR);                  /* illegal characters */
X   inputString[count] = '\0';        /* set terminating character */
X   switch(SetTapeTM(turingMachine, inputString))
X   {
X     case IllegalSymbol : Errors(5, NOLINENR);
X                          break;
X     case NoError       : /* empty */ ;
X                          break;
X     default            : Errors(16, NOLINENR);
X   }
X}
X
X/* --------------------------------------------------------------------------
X     EOF tursim.c
X-------------------------------------------------------------------------- */
END_OF_FILE
  if test 13741 -ne `wc -c <'tursim/tursim.c'`; then
    echo shar: \"'tursim/tursim.c'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/tursim.c'
  # end of 'tursim/tursim.c'
fi
if test -f 'tursim/tursim.mak' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/tursim.mak'\"
else
  echo shar: Extracting \"'tursim/tursim.mak'\" \(222 characters\)
  sed "s/^X//" >'tursim/tursim.mak' <<'END_OF_FILE'
Xtursim.exe: tursim.c turing.obj
X   tcc tursim.c turing.obj tape.obj trans.obj
X   
Xturing.obj: turing.c tape.obj trans.obj 
X   tcc -c turing.c
X   
Xtape.obj: tape.c
X   tcc -c tape.c
X   
Xtrans.obj:  trans.c
X   tcc -c trans.c
END_OF_FILE
  if test 222 -ne `wc -c <'tursim/tursim.mak'`; then
    echo shar: \"'tursim/tursim.mak'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/tursim.mak'
  # end of 'tursim/tursim.mak'
fi
if test -f 'tursim/tursim.man' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'tursim/tursim.man'\"
else
  echo shar: Extracting \"'tursim/tursim.man'\" \(6387 characters\)
  sed "s/^X//" >'tursim/tursim.man' <<'END_OF_FILE'
XNAME
X    tursim - simulates a single tape deterministic Turing-Machine
X
XSYNOPSIS
X    tursim file
X
XDESCRIPTION
X    tursim simulates a single tape deterministic Turing-Machine according to
X    the information specified in file. The output of the simulation is
X    written to the standard output.
X
X    Options
X        file    Contains two sections: 
X                -   the first section is an obligatory header which provides 
X                    all relevant information for the simulation
X                -   the second one contains all necessary transitions to
X                    execute the machine
X
X    Header
X        A list of identifiers as shown below. They should be placed in
X        the same order, one per line. Spaces are allowed but empty lines 
X        are not.
X
X        e.g.
X
X        INPUTFILE   = input.tur     /* file containing the inputstring  */
X        TAPELENGTH  = 30            /* maximum tape-length              */
X        MAXSTATES   = 10            /* number of states                 */
X        INITSTATE   = 10            /* initial-state number             */  
X        HALTSTATE   = 5             /* halt-state number                */
X        BLANK       = .             /* character representing a blank   */
X
X        Maximum values for TAPELENGTH and MAXSTATES are bound to the memory-
X        capacity of the computer-system, especially when running on a MS-DOS
X        system.
X
X    Transitions
X        A list of transition-functions (see example), one per line.
X        Spaces are allowed, empty lines not. Transitions may not be spread
X        over several lines. A line starting with ";" is treated as a comment.
X        
X
X        Syntax: d(current state, current symbol) = (new state, new symbol)
X
X                state =             cardinal number, 0 < state <= MAXSTATES
X                                    (MAXSTATES <= 255)
X                current symbol =    character of ASCII-set, except R and L
X                new symbol =        character of ASCII-set: R = move tapehead
X                                    right, L = move tapehead left, other
X                                    symbol = write this symbol, there are
X                                    also some special transitions (see below)
X
X        e.g.    d(10,y) = (10,R)    
X                ; this is a comment
X                d(9,y)  = (2,y)
X
X        Special transitions:
X
X        e.g.
X            d(10,~x)    =   (10,R)  /* for all symbols not equal to x   */
X            d(10,&)     =   (10,R)  /* for all symbols                  */
X
X        The construction "not for all symbols" (~&) is not allowed because it
X        makes no sense.
X        A single "~" is also not allowed in order to prevent ambiguities.
X
X    Input-file
X        Contains the input for the Turing-Machine = a string of characters
X        which will be written on the tape. This string starts at the first
X        position of the file and ends at the first white-space character
X        (space, tab, enter). Every possible character in the ASCII-set is
X        allowed except the characters R, L, ~, & and the control-characters 
X	(LF, FF,...).
X
XEXAMPLES
X    To show a paged output (MS-DOS && UNIX):
X
X        tursim oddeven.tur | more
X
X    To write the output to a file (MS-DOS && UNIX):
X
X        tursim oddeven.tur > output_file
X
XWARNINGS
X    Use no tape longer than 79 characters if sending the output to the
X    screen. A wrap-around will occur and it's impossible to distinguish the
X    place where the tapehead is pointing to.
X    Use no tape longer than the maximum line length of your favourite editor
X    if sending the output to a file.
X    A common cause of errors is the use of the "~"-symbol. e.g.
X
X        d(1,~x)     =   (1,R)
X        d(1,y)      =   (2,L)
X
X    This construction generates an error because in the first line a
X    transition is created from state 1 to state 1 for all symbols not equal
X    to "x", which includes the symbol "y". In the second line, the transition
X    from state 1 to state 1 for symbol "y" is changed, which causes an error
X    (transition already in use) because this is only possible for a non-
X    deterministic machine.
X
X
XDIAGNOSTICS
X    inputstring too long for tape
X        the inputstring is longer than the tape, try to increase TAPELENGTH
X    inputstring contains illegal characters 
X        the inputstring contains one of the following characters &, ~, R or L
X    while inserting transition in line ???  
X        an error occured during the insertion of a new transition, more
X        specific errors are generated when necessary
X    transition already in use
X        only one unique transition for every state-symbol pair is allowed
X    wrong construction of header in line ???
X        an error in the header (wrong number of identifiers, misspelling the
X        name of identifiers, wrong order,... )
X    during initialisation of turing-machine
X        out of memory is the most common cause (use less states or make the
X        tape smaller) 
X
XIMPLEMENTATION
X    The program is written in ANSI-C. To increase readibility, reusability
X    and reliability the program is split up in 4 different modules:
X        tape.h && tape.c        =   Implementation of an entire tape-system
X                                    with n tapes
X        trans.h && trans.c      =   Implementation of a transition-matrix
X        turing.h && turing.c    =   Implementation of a deterministic one-
X                                    tape Turing Machine, is a client of the
X                                    two previous modules
X        tursim.c                =   the main program, is a client of the
X                                    previous module, reads input, executes
X                                    the machine and sends output to the
X                                    standard output
X
X    Compiling:
X        UNIX            make
X        MS-DOS          make -ftursim.mak
X
X    All modules are fully documented and don't need much explanation.
X    All transitions are stored in a transition-matrix. The advantage of this
X    implementation is that the time needed to find the right transition is
X    constant (constant time-complexity) but its greatest drawback is the
X    large space-complexity as there is a place reserved for every possible
X    transition (also for transitions which are never used).
X
XAUTHORS
X    Herman Horsten && Sven Boden
END_OF_FILE
  if test 6387 -ne `wc -c <'tursim/tursim.man'`; then
    echo shar: \"'tursim/tursim.man'\" unpacked with wrong size!
  fi
  chmod +x 'tursim/tursim.man'
  # end of 'tursim/tursim.man'
fi
echo shar: End of archive 1 \(of 1\).
cp /dev/null ark1isdone
MISSING=""
for I in 1 ; do
    if test ! -f ark${I}isdone ; then
	MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have the archive.
    rm -f ark[1-9]isdone
else
    echo You still must unpack the following archives:
    echo "        " ${MISSING}
fi
exit 0
exit 0 # Just in case...

