tmsim

  1/*
  2 * Copyright © 2016-2018 Sören Tempel
  3 *
  4 * This program is free software: you can redistribute it and/or
  5 * modify it under the terms of the GNU Affero General Public
  6 * License as published by the Free Software Foundation, either
  7 * version 3 of the License, or (at your option) any later version.
  8 *
  9 * This program is distributed in the hope that it will be useful,
 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 12 * Affero General Public License for more details.
 13 *
 14 * You should have received a copy of the GNU Affero General Public
 15 * License along with this program. If not, see
 16 * <http://www.gnu.org/licenses/>.
 17 */
 18
 19#ifndef TMSIM_TURING_H
 20#define TMSIM_TURING_H
 21
 22#include <sys/types.h>
 23
 24enum {
 25	/**
 26	 * Amount of buckets used for the state map.
 27	 */
 28	STATEMAPSIZ = 128,
 29
 30	/**
 31	 * Amount of buckets used for the transition map.
 32	 */
 33	TRANSMAPSIZ = 16,
 34
 35	/**
 36	 * Amount of space allocated for accepting states with realloc.
 37	 */
 38	ACCEPTSTEP = 8,
 39
 40	/**
 41	 * Character used to represent blanks on the tape.
 42	 */
 43	BLANKCHAR = '$',
 44};
 45
 46/**
 47 * Type used for turing machine state names.
 48 */
 49typedef int tmname;
 50
 51/**
 52 * Enum describing direction head should be moved in.
 53 */
 54typedef enum {
 55	RIGHT, /**< Move head right. */
 56	LEFT,  /**< Move head left. */
 57	STAY,  /**< Don't move head at all. */
 58} direction;
 59
 60typedef struct _tmstate tmstate; /**< State of a turing machine. */
 61typedef struct _tmtrans tmtrans; /**< Transition from one state to another. */
 62
 63/**
 64 * Type used as a key for the ::tmmap.
 65 */
 66typedef int mapkey;
 67
 68/**
 69 * Entry in a bucket hashing implementation.
 70 */
 71typedef struct _mapentry mapentry;
 72
 73struct _mapentry {
 74	mapkey key; /**< Key of this entry. */
 75
 76	/**
 77	 * If there was a hash collision bucket hashing is used which means
 78	 * we will use a linked list for this key. This element points to the
 79	 * next element in the linked list. If there wasn't a hash collision for
 80	 * the given key so far this field has the value NULL.
 81	 */
 82	mapentry *next;
 83
 84	union {
 85		tmstate *state; /**< Used if this entry stores a tmstate. */
 86		tmtrans *trans; /**< Used if this entry stores a tmtrans. */
 87	} data;
 88};
 89
 90/**
 91 * Bucket hashing implementation.
 92 */
 93typedef struct _tmmap tmmap;
 94
 95struct _tmmap {
 96	size_t size;        /**< Amount of buckets which should be used. */
 97	mapentry **entries; /**< Pointer pointing to entry pointers. */
 98};
 99
100struct _tmstate {
101	tmname name;  /**< Name of this tmstate. */
102	tmmap *trans; /**< Transitions for this state. */
103};
104
105struct _tmtrans {
106	/**
107	 * Symbol which needs to be read to trigger this transition.
108	 */
109	char rsym;
110
111	/**
112	 * Symbol which should be written on the tape when performing this
113	 * tranisition. The symbol which triggers this transition is not
114	 * stored in this struct and is used as a key in the tmmap instead.
115	 */
116	char wsym;
117
118	/**
119	 * Direction to move head to after performing this transition.
120	 */
121	direction headdir;
122
123	/**
124	 * Name of the state the turing machine switches to after writing
125	 * the associated symbol to the tape and moving the head to the
126	 * associated direction.
127	 */
128	tmname nextstate;
129};
130
131/**
132 * Double linked list used for entries on the tape of the turing machine.
133 */
134typedef struct _tapeentry tapeentry;
135
136struct _tapeentry {
137	char value;      /**< Symbol for this tape entry. */
138	tapeentry *next; /**< Entry on the right-hand side of this one. */
139	tapeentry *prev; /**< Entry on the left-hand side of this one. */
140};
141
142/**
143 * Deterministic turing machine implementation.
144 */
145typedef struct _dtm dtm;
146
147struct _dtm {
148	tapeentry *tape; /**< Tape content. */
149	tmmap *states;   /**< Map of all states. */
150	tmname start;    /**< Initial state. */
151
152	tmname *accept;   /**< Pointer to array of accepting states. */
153	size_t acceptsiz; /**< Amount of accepting states. */
154};
155
156dtm *newtm(void);
157tmstate *newtmstate(void);
158void addaccept(dtm *, tmname);
159
160int addtrans(tmstate *, tmtrans *);
161int gettrans(tmstate *, char, tmtrans **);
162
163int addstate(dtm *, tmstate *);
164int getstate(dtm *, tmname, tmstate **);
165
166void writetape(dtm *, char *);
167void printtape(dtm *);
168
169void eachstate(dtm *, void (*fn)(tmstate *, void *), void *);
170void eachtrans(tmstate *, void (*fn)(tmtrans *, tmstate *, void *), void *);
171
172int runtm(dtm *);
173int dirstr(direction);
174int verifyinput(char *, size_t *);
175
176#endif