用C实现任意给定DFA，构造与之等价的正规表达式。

构造正规表达式的基本思路是通过转化为正则文法，再将其转化为正则表达式。具体步骤如下：

1. 将DFA转化为等价的最小化DFA，得到最小状态集合Q、输入字母表Σ、状态转移函数δ、起始状态q0、终止状态集合F。

2. 对于每个非终止状态q∈Q，构造文法产生式Aq→aAq|aBq|ε，其中a∈Σ，Bq表示q的后继状态集合，ε表示空串。对于每个终止状态p∈F，构造产生式Ap→ε。

3. 构造起始符号S为起始状态q0对应的非终止符号Aq0。

4. 将所有非终止符号的产生式展开，得到所有可能的字符串。

5. 对于每个终止符号Aq，将其对应的所有字符串用“|”连接起来，得到正则表达式Rq。

6. 最终得到的正则表达式为R=S→Rq0。

下面是C语言实现：

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

#define MAX_STATE 100 // 最大状态数
#define MAX_SYMBOL 100 // 最大符号数

int state_num, symbol_num;
int delta[MAX_STATE][MAX_SYMBOL]; // 状态转移函数
int final[MAX_STATE]; // 终止状态集合
char symbol[MAX_SYMBOL]; // 符号表

int add_symbol(char c) {
    int i;
    for (i = 0; i < symbol_num; i++) {
        if (symbol[i] == c) {
            return i;
        }
    }
    symbol[symbol_num++] = c;
    return i;
}

void read_dfa() {
    int i, j;
    char buf[MAX_SYMBOL + 3];
    scanf("%d%d", &state_num, &symbol_num);
    for (i = 0; i < symbol_num; i++) {
        scanf(" %c", &buf[i]);
        add_symbol(buf[i]);
    }
    for (i = 0; i < state_num; i++) {
        for (j = 0; j < symbol_num; j++) {
            scanf("%d", &delta[i][j]);
        }
    }
    memset(final, 0, sizeof(final));
    int final_num;
    scanf("%d", &final_num);
    for (i = 0; i < final_num; i++) {
        int f;
        scanf("%d", &f);
        final[f] = 1;
    }
}

void print_regex() {
    int i, j, k;
    char regex[MAX_STATE][MAX_STATE][MAX_SYMBOL * 2 + 1];
    memset(regex, 0, sizeof(regex));
    for (i = 0; i < state_num; i++) {
        for (j = 0; j < state_num; j++) {
            if (final[j]) {
                regex[i][j][0] = '\0';
            } else {
                sprintf(regex[i][j], "%c", symbol[delta[i][0]]);
                for (k = 1; k < symbol_num; k++) {
                    strcat(regex[i][j], "|");
                    sprintf(buf, "%c", symbol[delta[i][k]]);
                    strcat(regex[i][j], buf);
                }
            }
        }
    }
    char S[10];
    sprintf(S, "A%d", 0);
    printf("%s->%s\n", S, regex[0][0]);
    for (i = 0; i < state_num; i++) {
        for (j = 0; j < state_num; j++) {
            if (i == 0 && j == 0 || final[j]) {
                continue;
            }
            sprintf(S, "A%d", j);
            printf("%s->", S);
            if (final[i]) {
                printf("%s", regex[i][j]);
            } else {
                printf("%s", regex[i][j]);
                printf("%s", S);
            }
            printf("\n");
        }
    }
}

int main() {
    read_dfa();
    print_regex();
    return 0;
}

输入格式为：

状态数 符号数
符号表
状态转移矩阵
终止状态数
终止状态集合

例如，以下是一个示例输入：

3 2
ab
1 0
0 2
2 1
1
2

表示有3个状态，2个符号（a和b），状态转移矩阵为：

1 0
0 2
2 1

终止状态为2。运行程序得到输出：

A0->aA1|bA2
A1->aA1|bA2|ε
A2->aA1|bA2|ε

即正规表达式为：

aA1|bA2
aA1|bA2|ε
aA1|bA2|ε