我刚在网上找到这段代码，不明白应该如何格式化输入。此处显示了来自同一程序员的类似输入示例:Pushdown automaton implemented in C
但还是没有太大帮助。这是它说的:
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.
谁能提供一些如何处理输入的指导？我现在非常努力地尝试了大约 6 个小时，但我终其一生都无法破译此代码的输入格式。
用 gcc 编译后，只需执行“./executable”并按回车键即可运行它。然后粘贴示例输入字符串，如上所示(尽管对于此程序我需要不同的输入)。
/* 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;
}
最佳答案
线的大量使用buffer = strtok(NULL,":")确认输入字符串(就像在链接到的代码中一样)以冒号分隔。
结构定义是对输入进行逆向工程的关键。
主要结构是:
typedef struct tm {
char *input_alpha;
char *input;
char *tape_alpha;
char start;
char accept;
char reject;
List *transition;
} TM;
函数createTM()是在 : 上拆分输入的函数并加载图灵机。 struct tm有 7 个字段和 createTM()有7个清晰的阶段
1) 第一部分是输入字母表。大概这将是一个包含 1 个或多个字符的字符串，例如01 .
2) 第二部分是磁带是磁带字母表。其中唯一在其余代码中起作用的字符是第一个字符。线路const char blank = m->tape_alpha[0];主仿真函数中的 表示第一个字符起空白字符的作用——表示磁带方 block 为空的字符。将空白写入正方形的能力允许图灵机删除正方形中的数据。请注意，在某种意义上，这部分输入是乱序的——它被列为结构定义中的第三个字段，但却是输入字符串中的第二个字段。
3) 第三部分是磁带上的初始输入。它是一个字符串，其所有字符都来自第一部分。函数is_valid_input()用于检查此条件。
4) 接下来是起始状态，由一个字符组成
5) 下一部分是接受状态，同样是单个字符。因此，在这个 TM 模型中，只有一个接受状态
6) 接下来是拒绝状态，同样用一个字符表示
7) 接下来是一个字符串序列，输入一个字符串链表。理解其工作原理的关键函数是 get_transition()它采用这些转换字符串之一并将其转换为 Transition结构，声明为:
typedef struct transition {
char current_state;
char tape_symbol;
char new_state;
char new_tape_symbol;
Direction dir;
} Transition;
仔细看函数get_transition()您可以推断出转换由长度为 5 的字符串表示，其中最后一个字符是 R或 L .一个例子类似于 a1b0R上面写着类似“如果您在状态 a 时扫描符号 0，转换到状态 b，写入符号 1 并向右移动”。
将它们放在一起，输入字符串的形式类似于:
01:_102:1001010101:$:a:r:$0b1R:b1b0L:a1b2R
对应于
01 _102 1001010101 $ a r $0b1R b1b0L a1b2R
input tape input start accept reject transitions
| alphabets | | states |
(blank = '_')
我只是随机进行了一些转换，既不知道也不关心程序将如何处理这个输入。这应该足以让您开始试验该程序。
关于无法理解 C 中图灵机实现的输入，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41172203/