Cannot understand input of a Turing Machine Implementation in C

Question

I just found this code online, and do not understand how the input should be formatted. An example of similar input from the same programmer is shown here: Pushdown automaton implemented in C

But it still does not help that much. Here is what it says:

The input format is like: e01:e0$:000111:a:ad:aeeb$:b0eb0:b10ce:c10ce:ce$de The input is separated by a semicolon “:”, first section is “input alphabet”, second is “stack alphabet”, then “input” and the last whole bunch are transition functions.

Can anyone provide some guidance how the input is handled? I am trying really hard for about 6 hours now, and cannot for the life of me decipher how the input should be formatted for this code.

Once it is compiled with gcc, to run it just do "./executable" and press enter. Then paste in the sample input string as shown above (although for this program I would need a different input).

/* This C file implements a Turing Machine
 * author: Kevin Zhou
 * Computer Science and Electronics
 * University of Bristol
 * Date: 21st April 2010
 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct tapes {
    struct tapes *left;
    struct tapes *right;
    char content;
} Tape;

typedef enum { LEFT,RIGHT } Direction;

typedef struct transition {
    char current_state;
    char tape_symbol;
    char new_state;
    char new_tape_symbol;
    Direction dir;
} Transition;

typedef struct list {
    Transition *content;
    struct list *next;
} List;

typedef struct tm {
    char *input_alpha;
    char *input;
    char *tape_alpha;
    char start;
    char accept;
    char reject;
    List *transition;
} TM;

Tape *insert_tape(Tape *t, Direction dir, char c) {
    Tape *head = t;
    Tape *new1 = calloc(1,sizeof(Tape));;
    new1 -> content = c;
    if(dir == LEFT) {
        while(t->left != NULL) {
            t = t->left;
        }
        new1->right = t;
        new1->left = NULL;
        t->left = new1;
        return new1;
    }
    if(dir == RIGHT) {
        while(t->right != NULL) {
            t = t->right;
        }
        new1->left = t;
        new1->right = NULL;
        t->right = new1;
    }
    return head;
}

Tape *create_tape(char *input) {
    int i=1;
    Tape *t = calloc(1,sizeof(Tape));
    t->content = input[0];
    while(1) {
        if(input[i] == '\0') break;
        t = insert_tape(t,RIGHT,input[i]);
        i++;
    }
    return t;
}

/* turn the input string into Transition fields */
Transition *get_transition(char *s) {
    Transition *t = calloc(1,sizeof(Transition));
    Direction dir;
    t->current_state = s[0];
    t->tape_symbol = s[1];
    t->new_state = s[2];
    t->new_tape_symbol = s[3];
    dir = (s[4]=='R')? RIGHT:LEFT;
    t->dir = dir;
    return t;
}

/* turn the string into transitions and add into list */
List *insert_list( List *l, char *elem ) {
    List *t = calloc(1,sizeof(List));
    List *head = l;
    while(l->next!=NULL)
        l = l->next;
    t->content = get_transition(elem);
    t->next = NULL;
    l->next = t;
    return head;
}

/* insert a transition into a list */
List *insert_list_transition( List *l, Transition *tr) {
    List *t = calloc(1,sizeof(List));
    List *head = l;
    while(l->next!=NULL)
        l = l->next;
    t->content = tr;
    t->next = NULL;
    l->next = t;
    return head;
}

void print_tape( Tape *t,char blank) {
    char c;
    while(1) {
        if(t->content != blank) break;
        t= t->right;
    }
    while(1) {
        if(t==NULL) break;
        c = t->content;
        if(t->content != blank)
            putchar(c);
        t= t->right;
    }
    putchar('\n');
}

void print_transition (Transition *t) {
    char s1[] = "Left";
    char s2[] = "Right";
    if(t==NULL) {
        printf("NULL Transfer");
        return;
    }
    printf("current:%c tape:%c new state:%c new tape:%c direction %s\n",t->current_state,t->tape_symbol,t->new_state,t->new_tape_symbol,(t->dir == LEFT)?s1:s2);
}

/*test if the char c is in the string s */
int contains ( char c, char *s ) {
    int i=0;
    while(1) {
        if(c== s[i]) return 1;
        if(s[i] == '\0') return 0;
        i++;
    }
}

/* test if the input is a valid input */
int is_valid_input( char *input_alpha, char *input ) {
    int i=0;
    char c;
    while(1) {
        c = input[i];
        if(c == '\0') break;
        if(!contains(c,input_alpha)) return 0;
        i++;
    }
    return 1;
}

TM *createTM (char *input) {

    TM *m = calloc(1,sizeof(TM));
    List *tr = calloc(1,sizeof(List));
    char *buffer;
    /*read input alphabet of PDA*/
    buffer = strtok(input,":");
    if(buffer == NULL) {
        printf("Error in reading input alphabet!\n");
        exit(1);
    }
    m->input_alpha = buffer;

    /*read tape alphabet*/
    buffer = strtok(NULL,":");

    if(buffer == NULL) {
        printf("Error in reading tape alphabet!\n");
        exit(1);
    }
    m->tape_alpha = buffer;

    /*read input sequence*/
    buffer = strtok(NULL,":");
    if(buffer == NULL) {
        printf("Error in reading input sequence!\n");
        exit(1);
    }

    if(!is_valid_input(m->input_alpha,buffer)) {
        printf("Error! Input contains some invalid characters that don't match the input alphabet!\n");
        exit(1);
    }

    m->input = buffer;
    buffer = strtok(NULL,":");
    m->start = buffer[0];
    buffer = strtok(NULL,":");
    m->accept = buffer[0];
    buffer = strtok(NULL,":");
    m->reject = buffer[0];

    /*read tape transition*/
    while(1) {
        buffer = strtok(NULL,":");
        if(buffer == NULL) break;
        tr = insert_list(tr,buffer);
    }

    m->transition = tr->next;
    return m;
}

Transition *find_transition(List * list,char state, char tape_symbol) {
    Transition *t;
    while(1) {
        if(list==NULL) return NULL;
        t = list -> content;
        if(t->current_state == state && t->tape_symbol == tape_symbol)
            return t;
        list = list->next;
    }
}

Tape *move(Tape *t,Direction dir, char blank) {
    if(dir == LEFT) {
        if(t->left==NULL) {
            t = insert_tape(t,LEFT,blank);
        }
        return t->left;
    }
    if(dir == RIGHT) {
        if(t->right==NULL) {
            t = insert_tape(t,RIGHT,blank);
        }
        return t->right;
    }
    return NULL;
}

void simulate( TM *m ) {
    /* first symbol in input symbol used to represent the blank symbol */
    const char blank = m->tape_alpha[0];
    char current_state = m->start;
    Tape *tape = create_tape(m->input);
    Tape *current_tape = tape;
    char current_tape_symbol;
    Transition *current_transition;
    while(1) {
        if(current_state == m->accept) {
            printf("Accept\n");
            print_tape(tape,blank);
            break;
        }
        if(current_state == m->reject) {
            printf("Reject\n");
            print_tape(tape,blank);
            break;
        }
        current_tape_symbol = (current_tape==NULL||current_tape ->content == '\0')?blank:current_tape->content;
        current_transition = find_transition(m->transition,current_state,current_tape_symbol);
        current_state = current_transition -> new_state;
        current_tape -> content = current_transition -> new_tape_symbol;
        current_tape = move( current_tape, current_transition ->dir, blank);
    }
}

int main(void) {
    char s[300];
    TM *p;
    scanf("%s",s);
    p = createTM(s);
    simulate(p);
    return 0;
}

Answer 1

The heavy use of the line buffer = strtok(NULL,":") confirms that the input strings are (like in the linked-to code) colon-delimited.

The struct defintions are the key to reverse-engineering the input.

The main struct is:

typedef struct tm {
    char *input_alpha;
    char *input;
    char *tape_alpha;
    char start;
    char accept;
    char reject;
    List *transition;
} TM;

The function createTM() is the function which splits the input on : and loads the Turing machine. struct tm has 7 fields and createTM() has 7 clear phases

1) The first part is the input alphabet. Presumably this would be a string of 1 or more characters, e.g. 01.

2) The second part is the tape is the tape alphabet. The only character in this which plays any role in the rest of the code is the first character. The line const char blank = m->tape_alpha[0]; in the main simulation function indicates that the first character plays the role of the blank character -- the character which indicates that a tape square is empty. The ability to write the blank to a square allows the Turing machine to erase the data in a square. Note that in some sense this part of the input is out of order -- it is listed as the third field in the struct definition but is the second field in the input string.

3) The thirs part is the initial input on the tape. It is a string all of whose characters are drawn from the first part. The function is_valid_input() is used to check this condition.

4) The next part is the start state, which consists of a single char

5) The next part is the accept state, which is again a single char. Thus, in this model of a TM there is a single accepting state

6) The next part is the rejecting state, which is again represented by a single char

7) What follows is a sequence of strings, fed into a linked list of strings. The key function in understanding how it works is get_transition() which takes one of these transition strings and converts it into a Transition struct, declared as:

typedef struct transition {
    char current_state;
    char tape_symbol;
    char new_state;
    char new_tape_symbol;
    Direction dir;
} Transition;

Looking carefully at the function get_transition() you can infer that a transition is represented by a string of length 5 where the last char is either R or L. An example would be something like a1b0R which says something like "if you are in state a while scanning symbol 0, transition to state b, write symbol 1 and the move to the right".

Putting it all together, the form of an input string would be something like:

01:_102:1001010101:$:a:r:$0b1R:b1b0L:a1b2R

corresponding to

   01    _102    1001010101     $       a       r       $0b1R    b1b0L    a1b2R
 input   tape      input      start  accept  reject          transitions
|  alphabets |                 |     states        | 
(blank = '_')    

I just made some transitions at random, and neither know nor care what the program would do with this input. This should be enough for you to start experimenting with the program.