Theory of computation : Write a method that emulates a general Turing machine. T

Question

Theory of computation : Write a method that emulates a general Turing machine. The input to this method should include: the number N of states q0, ..., qN 1; we assume that q0 is the start state, that the last-but-one state qN 2 is the accept state, and the last state qN 1 is the reject state; the number M of symbols s0, ... sM 1; we assume that s0 is the blank state _; an integer array state[n][m] that describes to what state the Turing machine moves if it was in the state qn and sees the symbol sm; an integer array symbol[n][m] that describes what symbol should be written on the tape if the Turing Machine in the state qn sees the symbol sm; a character array lr[n][m] that describes, for each state qn and for each symbol sm, whether the Turing machine moves to the left (L), or to the right (R), or stays in place (blank symbol); the integer array of a large size describing the original contents of the tape, i.e., what symbols are written in each cell. This program needs to keep track of a current location of the head. Initially, this location is 0. Your program should emulate the work of the Turing machine step-by-step. Return the printout of the method, the printout of the program that you used to test this method, and the printout of the result of this testing. Example: A Turing machine for checking whether a binary string is even (i.e., ends with 0) has the following rules: start, _ --> inNumber, R inNumber, 1 --> state1, R inNumber, _ --> reject inNumber, 0 --> state0, R state0, 1 --> state1, R state0, 0 --> state0, R state1, 1 --> state1, R state1, 0 --> state0, R state1, _ --> reject state0, _ --> accept In this case: we have N = 7 states: q0 = start, q1 = inNumber, q2 = state1, q4 = state0, q5 = accept, and q6 = reject; we have M = 3 symbols: s0 = _, s1 = 0, and s2 = 1; Here: The first rule start, _ --> inNumber, R means that state[0][0] = 1, symbol[0][0] = 0, and lr[0][0] = R. The second rule inNumber, 1 --> state1, R means that state[1][2] = 2, symbol[1][2] = 2, and lr[1][2] = R, etc.

Explanation / Answer

Below is the code for the requested Turing Machine . Hope it helps!!!

#include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX_LENGTH 1000 #define STR_LENGTH 100 #define LIMIT 5 #define FILENAME_LENGTH 20 void print_head(); void print_message(); void print_line(); void update_string(char, char); char string[STR_LENGTH]; int head, string_length; int main(int argc, char *argv[]) { int limit, i, flag; char current_state[MAX_LENGTH][LIMIT], new_state[MAX_LENGTH][LIMIT]; char input_symbol[MAX_LENGTH], write_symbol[MAX_LENGTH], move[MAX_LENGTH]; char state[LIMIT], file_name[FILENAME_LENGTH]; FILE *fout, *fin; printf(" TURING MACHINE "); if(argc > 1 && !strcmp(argv[1], "-help")) { printf("Usage "); printf("1. turingmachine "); printf("2. turingmachine <input file> "); printf("3. turingmachine <input file> <input string> "); exit(0); } /* Reading data from user */ if(argc > 1) /* Checks if file input as commandline argument is present */ { fin = fopen(argv[1], "r"); if(fin == NULL) { printf("File not found: '%s' ", argv[1]); exit(0); } for(limit = 0 ; limit < MAX_LENGTH ; limit++) { fscanf(fin, "%s", current_state[limit]); if(!strcmp(current_state[limit], "$")) break; fscanf(fin, " %c %c %c %s ", &input_symbol[limit], &write_symbol[limit], &move[limit], new_state[limit]); } } else { print_message(); for(limit = 0 ; limit < MAX_LENGTH ; limit++) { scanf("%s%s", current_state[limit], current_state[limit]); if(!strcmp(current_state[limit], "$")) break; scanf(" %c %c %c %s", &input_symbol[limit], &write_symbol[limit], &move[limit], new_state[limit]); } printf(" "); } if(argc > 2) /* Checks if string input as commandline argument is present */ { strcpy(string, argv[2]); } else { printf("Enter input string : "); scanf("%s", string); } string_length = strlen(string); printf(" "); /* Start trasition operations */ head = 0; strcpy(state, current_state[0]); while(1) { flag = 0; for(i = 0 ; i < limit ; i++) { if(!strcmp(state, current_state[i]) && string[head] == input_symbol[i]) { update_string(write_symbol[i], move[i]); strcpy(state, new_state[i]); printf("%-10s | state = %s ", string, new_state[i]); if(!strcmp(state, "#")) flag = 2; else flag = 1; break; } } if(flag == 0) { printf("No production found for input symbol '%c' at state '%s'. Turing Machine halted! ", string[head], state); break; } else if(flag == 2) { printf("Accepted! Turing Machine halted! "); break; } } printf(" "); printf("Output is stored as '%s' in the folder ", file_name); return 0; } void update_string(char symbol, char move) { int i; string[head] = symbol; if(move == 'r') head++; else if(move == 'l') head--; if(head == -1) { for(i = string_length ; i > 0 ; i--) string[i] = string[i - 1]; string[0] = '_'; string_length++; string[string_length] = ''; head = 0; } else if(head == string_length) { string[string_length] = '_'; string_length++; string[string_length] = ''; } } void print_message() { printf("Enter the Turing Machine input code "); printf("Input format: "); printf("<current state> <input symbol> <new symbol> <movement> <new state> "); printf("A single transition should occupy a single line "); printf("input symbol, new symbol and movement are single characters. "); printf("current state and new state can be any combination of characters within a limit of 5 "); printf("First current state will be considered as your initial state "); printf("Use '_' for blank, '#' for halting state "); printf("Use '$' as current state to stop. "); }

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.