模拟一个DFA的执行,设计c/c++程序,满足如下要求: 输入:0和1组成的符号串 s 输出:s是否能被M识别, 若s能被M识别,则输出 识别s所经历的状态顺序。否则,输出“Error”。
时间: 2023-05-27 07:06:22 浏览: 53
#include <stdio.h>
#include <string.h>
#define MAX_STATE 100 // 最大状态数
#define MAX_LEN 1000 // 最大输入长度
int transition[MAX_STATE][2]; // 转移函数
int final_state[MAX_STATE]; // 终止状态
int state_num; // 状态数
void init_dfa() {
memset(transition, -1, sizeof(transition)); // 初始化转移函数
memset(final_state, 0, sizeof(final_state)); // 初始化终止状态
state_num = 0; // 初始化状态数
}
void add_transition(int from, int to0, int to1) {
transition[from][0] = to0;
transition[from][1] = to1;
}
void add_final_state(int state) {
final_state[state] = 1;
}
void print_path(int path[], int len) {
for (int i = 0; i < len; i++) {
printf("%d ", path[i]);
}
printf("\n");
}
int simulate(char s[]) {
int len = strlen(s);
int cur_state = 0; // 当前状态
int path[MAX_LEN]; // 经过的状态
int path_len = 0; // 经过的状态数
for (int i = 0; i < len; i++) {
int input = s[i] - '0';
if (transition[cur_state][input] == -1) { // 没有对应的转移
return 0;
}
path[path_len++] = cur_state;
cur_state = transition[cur_state][input];
}
path[path_len++] = cur_state;
if (final_state[cur_state]) { // 到达终止状态
print_path(path, path_len);
return 1;
} else {
return 0;
}
}
int main() {
init_dfa();
// 添加状态和转移
add_transition(0, 1, 2);
add_transition(1, 3, 4);
add_transition(2, 4, 3);
add_transition(3, 4, 4);
add_transition(4, 4, 4);
// 添加终止状态
add_final_state(3);
add_final_state(4);
char s[MAX_LEN];
scanf("%s", s);
if (simulate(s)) {
printf("Accepted\n");
} else {
printf("Error\n");
}
return 0;
}