c语言实现有穷自动机识别字符串

有穷自动机（DFA）是一种能够识别特定语言的计算模型，它可以根据事先确定的有限状态集合、输入字母表、状态转移函数和起始状态以及接受状态集合来进行字符串的识别。下面是使用C语言实现DFA识别字符串的示例代码：

#include <stdio.h>
#include <string.h>

#define STATE_NUM 3
#define CHAR_NUM 2

int transition[STATE_NUM][CHAR_NUM] = {
    {1, 0},     // 状态0，输入字符0转移到状态1，输入字符1转移到状态0
    {2, 0},     // 状态1，输入字符0转移到状态2，输入字符1转移到状态0
    {2, 2}      // 状态2，输入字符0或字符1都转移到状态2
};

int is_accepted[STATE_NUM] = {0, 0, 1};   // 状态2为接受状态

int dfa(char* str) {
    int state = 0;
    int i;
    for (i = 0; i < strlen(str); i++) {
        char c = str[i];
        if (c < '0' || c > '1') {
            return 0;   // 非法字符
        }
        state = transition[state][c - '0'];
    }
    return is_accepted[state];
}

int main() {
    char str[100];
    printf("请输入字符串：");
    scanf("%s", str);
    if (dfa(str)) {
        printf("该字符串被识别\n");
    } else {
        printf("该字符串不被识别\n");
    }
    return 0;
}

在这个示例代码中，我们定义了一个有3个状态、输入字母表为0和1的DFA，它可以识别所有以1结尾的二进制字符串。我们通过`transition`数组来定义DFA的状态转移函数，其中`transition[i][j]`表示在状态i输入字符j时转移到的状态；`is_accepted`数组定义了DFA的接受状态集合，其中下标为i的元素表示状态i是否为接受状态。

在`dfa`函数中，我们根据输入字符串和DFA的状态转移函数来进行状态转移，最终判断是否到达了DFA的接受状态。如果输入字符串中包含了非法字符，则直接返回0表示无法识别该字符串。

在`main`函数中，我们通过`scanf`函数获取用户输入的字符串，然后调用`dfa`函数来判断该字符串是否被DFA识别。如果被识别，则输出“该字符串被识别”，否则输出“该字符串不被识别”。