Download code

Jump to: navigation, search

Back to Turing_machine_simulator_(C)

Download for Windows: zip

Download for UNIX: zip, tar.gz, tar.bz2

test_driver.c

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Turing_machine_simulator_(C)?oldid=10481
 14 */
 15 
 16 #include <stdio.h>
 17 #include <stdlib.h>
 18 #include <string.h>
 19 #include "simulate_turing_machine.h"
 20 
 21 struct turing_machine get_example_turing_machine(void) {
 22     struct turing_machine machine;
 23     int i, j;
 24     machine.initial_control_state = 0;
 25     machine.blank_symbol = '#';
 26     machine.num_accepting_states = 1;
 27     machine.accepting_states = malloc(sizeof(int)*machine.num_accepting_states);
 28     if (machine.accepting_states == NULL) {
 29         printf("Out of memory");
 30         exit(-1);
 31     }
 32     machine.accepting_states[0] = 5;
 33     #define NUM_STATES 7
 34     #define STATE_INVALID 6
 35 
 36     machine.transition_table = malloc(sizeof(struct transition_result *) * NUM_STATES);
 37     if (machine.transition_table == NULL) {
 38         printf("Out of memory");
 39         exit(-1);
 40     }
 41     for (i=0; i<NUM_STATES; i++) {
 42         machine.transition_table[i] =
 43             malloc(sizeof(struct transition_result)*TAPE_ALPHABET_SIZE);
 44         if (machine.transition_table[i] == NULL) {
 45             printf("Out of memory");
 46             exit(-1);
 47         }
 48         for (j=0; j<TAPE_ALPHABET_SIZE; j++) {
 49             machine.transition_table[i][j].control_state = STATE_INVALID;
 50             machine.transition_table[i][j].write_symbol = machine.blank_symbol;
 51             machine.transition_table[i][j].dir = DIR_LEFT;
 52         }
 53     }
 54     machine.transition_table[0]['#'].control_state = 4;
 55     machine.transition_table[0]['#'].write_symbol  = '#';
 56     machine.transition_table[0]['#'].dir           = DIR_RIGHT;
 57 
 58     machine.transition_table[0]['a'].control_state = 1;
 59     machine.transition_table[0]['a'].write_symbol  = '#';
 60     machine.transition_table[0]['a'].dir           = DIR_RIGHT;
 61 
 62     machine.transition_table[4]['#'].control_state = 5;
 63     machine.transition_table[4]['#'].write_symbol  = '#';
 64     machine.transition_table[4]['#'].dir           = DIR_RIGHT;
 65 
 66     machine.transition_table[1]['a'].control_state = 1;
 67     machine.transition_table[1]['a'].write_symbol  = 'a';
 68     machine.transition_table[1]['a'].dir           = DIR_RIGHT;
 69 
 70     machine.transition_table[1]['b'].control_state = 1;
 71     machine.transition_table[1]['b'].write_symbol  = 'b';
 72     machine.transition_table[1]['b'].dir           = DIR_RIGHT;
 73 
 74     machine.transition_table[1]['#'].control_state = 2;
 75     machine.transition_table[1]['#'].write_symbol  = '#';
 76     machine.transition_table[1]['#'].dir           = DIR_LEFT;
 77 
 78     machine.transition_table[2]['b'].control_state = 3;
 79     machine.transition_table[2]['b'].write_symbol  = '#';
 80     machine.transition_table[2]['b'].dir           = DIR_LEFT;
 81 
 82     machine.transition_table[3]['a'].control_state = 3;
 83     machine.transition_table[3]['a'].write_symbol  = 'a';
 84     machine.transition_table[3]['a'].dir           = DIR_LEFT;
 85 
 86     machine.transition_table[3]['b'].control_state = 3;
 87     machine.transition_table[3]['b'].write_symbol  = 'b';
 88     machine.transition_table[3]['b'].dir           = DIR_LEFT;
 89 
 90     machine.transition_table[3]['#'].control_state = 0;
 91     machine.transition_table[3]['#'].write_symbol  = '#';
 92     machine.transition_table[3]['#'].dir           = DIR_RIGHT;
 93     return machine;
 94 }   
 95 
 96 int main(int argc, char* argv[]) {
 97     if (argc < 1 + 1) {
 98         printf("Syntax: simulate_turing_machine <input string>\n");
 99         return -1;
100     }
101     simulate(get_example_turing_machine(), strlen(argv[1]), argv[1]);
102     return 0;
103 }


hijacker
hijacker
hijacker
hijacker

simulate_turing_machine.c

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Turing_machine_simulator_(C)?oldid=10481
 14 */
 15 
 16 #include <stdlib.h>
 17 #include <stdio.h>
 18 #include <string.h>
 19 #include <ctype.h>
 20 #include "simulate_turing_machine.h"
 21 
 22 struct turing_machine_state {
 23     int control_state;
 24     int head_position;
 25     int tape_size;
 26     symbol* tape;
 27 }; /* This structure need not be public */
 28 struct turing_machine_state
 29 create_initial_state(int initial_control_state, int input_string_length, symbol* input_string) {
 30     struct turing_machine_state state;
 31     state.control_state = initial_control_state;
 32     state.head_position = 0; /* Initially at left end */
 33     state.tape_size = input_string_length;
 34     state.tape = malloc(sizeof(symbol)*input_string_length);
 35     if (state.tape == NULL) {
 36         printf("Out of memory");
 37         exit(-1);
 38     }
 39 
 40     memmove(state.tape, input_string, sizeof(symbol)*input_string_length);
 41     return state;
 42 }
 43 void free_state(struct turing_machine_state* state) {
 44     free(state->tape);
 45 }
 46 void update_state(struct turing_machine_state* state, int new_control_state,
 47                   enum direction dir, char write_symbol, char blank_symbol)
 48 {
 49     state->control_state = new_control_state;
 50     state->tape[state->head_position] = write_symbol;
 51     if (dir == DIR_LEFT && state->head_position > 0) {
 52         state->head_position--;
 53     } else { /* dir == DIR_RIGHT */
 54         state->head_position++;
 55     }
 56     if (state->head_position >= state->tape_size) {
 57         int i, old_tape_size = state->tape_size;
 58         symbol* new_tape = realloc(state->tape, old_tape_size*2 + 10);
 59         if (new_tape == NULL) {
 60             printf("Out of memory");
 61             exit(-1);
 62         }
 63         state->tape = new_tape;
 64         state->tape_size *= 2;
 65         for (i=old_tape_size; i < state->tape_size; i++) {
 66             state->tape[i] = blank_symbol;
 67         }
 68     }
 69 }
 70 void trace_state(struct turing_machine_state* state, symbol blank_symbol) {
 71     int i;
 72     for(i=0; i < TRACE_TAPE_CHARS && i < state->head_position; i++) {
 73         printf(" ");
 74     }
 75     if (i < TRACE_TAPE_CHARS) {
 76         printf("v"); /* points down */
 77     }
 78     printf("\n");
 79     for(i=0; i < TRACE_TAPE_CHARS; i++) {
 80         printf("%c", i < state->tape_size ? state->tape[i] : blank_symbol);
 81     }
 82     printf("\n");
 83 }
 84 
 85 
 86 int is_in_int_list(int value, int list_size, int list[]) {
 87     int i;
 88     for(i=0; i<list_size; i++) {
 89         if (list[i] == value) {
 90             return 1;
 91         }
 92     }
 93     return 0;
 94 }
 95 void simulate(struct turing_machine machine, int input_string_length, symbol* input_string) {
 96     struct turing_machine_state state = 
 97         create_initial_state(machine.initial_control_state, input_string_length, input_string);
 98     trace_state(&state, machine.blank_symbol);
 99 
100     while (!is_in_int_list(state.control_state, machine.num_accepting_states,
101                            machine.accepting_states)) {
102         struct transition_result next =
103             machine.transition_table[state.control_state]
104                                     [(int)state.tape[state.head_position]];
105         update_state(&state, next.control_state, next.dir,
106                      next.write_symbol, machine.blank_symbol);
107         trace_state(&state, machine.blank_symbol);
108     }
109     free_state(&state);
110 }
111 


hijacker
hijacker
hijacker
hijacker

simulate_turing_machine.h

 1 /* The authors of this work have released all rights to it and placed it
 2 in the public domain under the Creative Commons CC0 1.0 waiver
 3 (http://creativecommons.org/publicdomain/zero/1.0/).
 4 
 5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 
13 Retrieved from: http://en.literateprograms.org/Turing_machine_simulator_(C)?oldid=10481
14 */
15 
16 #ifndef _SIMULATE_TURING_MACHINE_H_
17 #define _SIMULATE_TURING_MACHINE_H_
18 
19 #define TAPE_ALPHABET_SIZE 256
20 
21 #define TRACE_TAPE_CHARS   78
22 
23 typedef char symbol;
24 
25 enum direction { DIR_LEFT, DIR_RIGHT };
26 
27 struct transition_result {
28     int control_state;
29     symbol write_symbol;
30     enum direction dir;
31 };
32 struct turing_machine {
33     int initial_control_state;
34     char blank_symbol;
35     int num_accepting_states;
36     int* accepting_states;    
37     struct transition_result** transition_table;
38 };
39 void simulate(struct turing_machine machine, int input_string_length, symbol* input_string);
40 
41 #endif /* #ifndef _SIMULATE_TURING_MACHINE_H_ */
42 


hijacker
hijacker
hijacker
hijacker

example_output.txt

 1 $ simulate_turing_machine ab
 2 v
 3 ab############################################################################
 4  v
 5 #b############################################################################
 6   v
 7 #b############################################################################
 8  v
 9 #b############################################################################
10 v
11 ##############################################################################
12  v
13 ##############################################################################
14   v
15 ##############################################################################
16    v
17 ##############################################################################


hijacker
hijacker
hijacker
hijacker