NFA2DFA

nfa2dfa.c

// </> convert NFA to DFA
// @hyrious
// 
// input:
// n m i1 i2 .. _ <- this '_' is reserved
// s1  m1 m2 .. m_
// ...
// sn  m1 m2 .. m_
// 
// example:
// 10 2 a b _
// 0    _ _ 1,7
// ...
// 9    5 4 7
// 
// output:
// 4 2 a b
// A   B C
// ...
// D   B C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define new(x) (x*)malloc(sizeof(x))
#define array(x,n) (x*)malloc(sizeof(x)*(n))
#define str(n) (char*)malloc(sizeof(char)*((n)+1))

typedef struct Edge {
  char from, input, to;
  struct Edge *next;
} Edge;
Edge *newEdge(char from, char input, char to) {
  Edge *ret = new(Edge);
  ret->from = from;
  ret->input = input;
  ret->to = to;
  ret->next = NULL;
  return ret;
}
void freeEdge(Edge *edge) {
  if (edge->next) freeEdge(edge->next);
  free(edge);
}

int n = 0, m = 0;           // 状态数 输入数
char *S = NULL, *I = NULL;  // 状态 输入
Edge *E = NULL;             // 边表 { 1 -> 2 (a) }
Edge *tail = NULL;          // 边表尾
void insEdge(char from, char input, char to) {
  if (!E)
    tail = E = newEdge(from, input, to);
  else
    tail = tail->next = newEdge(from, input, to);
}

void readnfa() {
  scanf("%d%d", &n, &m);
  S = str(n);
  S[n] = 0;
  I = str(m + 1);
  I[m + 1] = 0;
  char buff[20];
  for (int i = 0; i <= m; ++i) {
    scanf("%s", buff);
    I[i] = buff[0];
  }
  for (int j = 0; j < n; ++j) {
    scanf("%s", buff);
    S[j] = buff[0];
    for (int i = 0; i <= m; ++i) {
      scanf("%s", buff);
      if (buff[0] == '_') continue;
      int l = strlen(buff);
      for (char *p = buff; p - buff < l; p += 2)
        insEdge(S[j], I[i], *p);
    }
  }
}
void showEdges() {
  if (!E)
    return;
  for (Edge *p = E; p; p = p->next)
    printf("%c -> %c (%c)\n", p->from, p->to, p->input);
}
void shownfa() {
  if (!E)
    return;
  putchar('\n');
  puts("View graph online: https://dreampuf.github.io/GraphvizOnline");
  putchar('\n');
  puts("digraph NFA {");
  for (Edge *p = E; p; p = p->next)
    printf("  %c -> %c [label=\"%c\"];\n", p->from, p->to, p->input);
  puts("}");
}
// index of state s
int iS(char s) {
  if (!S)
    return -1;
  for (int i = 0; S[i]; ++i)
    if (S[i] == s)
      return i;
  return -1;
}
// ret[n] = "--++", which represents a set
char *closure(char *ret) {
  char *stack = str(n), top = 0;
  for (int i = 0; ret[i]; ++i)
    if (ret[i] == '+')
      stack[top++] = S[i];
  while (top) {
    char s = stack[--top];
    for (Edge *p = E; p; p = p->next)
      if (p->from == s && p->input == '_' && ret[iS(p->to)] != '+')
        ret[iS(stack[top++] = p->to)] = '+';
  }
  free(stack);
  return ret;
}
void putset(char *x) {
  putchar('{');
  for (int i = 0, c = 0; *x; ++i, ++x)
    if (*x == '+')
      printf(c++ ? ",%d" : "%d", i);
  putchar('}');
}
char *move(char *x, char a) {
  char *ret = memset(str(n), '-', n * sizeof(char));
  ret[n] = 0;
  char *stack = str(n), top = 0;
  for (int i = 0; i < n; ++i)
    if (x[i] == '+')
      stack[top++] = S[i];
  while (top) {
    char s = stack[--top];
    for (Edge *p = E; p; p = p->next)
      if (p->from == s && p->input == a && ret[iS(p->to)] != '+')
        ret[iS(p->to)] = '+';
  }
  free(stack);
  return ret;
}

typedef struct Node {
  char *s;
  char *move;
  struct Node *next;
} Node;
Node *D = NULL;
Node *newNode(char *s) {
  Node *ret = new(Node);
  ret->s = s;
  ret->move = str(m);
  ret->move[m] = 0;
  ret->next = NULL;
  return ret;
}
void freeNode(Node *p) {
  if (p->next)
    freeNode(p->next);
  free(p->s);
  free(p->move);
  free(p);
}
int Nodelen() {
  int s = 0;
  for (Node *p = D; p; p = p->next, ++s)
    ;
  return s;
}
// D.push(Node(s)).uniq! and returns Node(s)'s index
int Nup(char *s) {
  if (!D) {
    D = newNode(s);
    return 0;
  }
  int i = 0;
  for (Node *p = D; p; p = p->next, ++i) {
    if (strcmp(p->s, s)) {
      if (!p->next) {
        p->next = newNode(s);
        return ++i;
      }
    } else {
      free(s);
      return i;
    }
  }
}
void calcdfa() {
  D = newNode(memset(str(n), '-', n * sizeof(char)));
  D->s[0] = '+', D->s[n] = 0;
  closure(D->s);
  for (Node *p = D; p; p = p->next)
    for (int i = 0; i < m; ++i)
      p->move[i] = Nup(closure(move(p->s, I[i])));
}
void showdfa() {
  int s = 0;
  putchar('\n');
  puts("digraph DFA {");
  for (Node *p = D; p; p = p->next, ++s)
    for (int i = 0; i < m; ++i)
      printf("  %c -> %c [label=\"%c\"];\n", 'A' + s, 'A' + p->move[i], I[i]);
  puts("}");
}
void putdfa() {
  printf("%d %d", Nodelen(), m);
  for (int i = 0; i < m; ++i)
    printf(" %c", I[i]);
  putchar('\n');
  int s = 0;
  for (Node *p = D; p; p = p->next, ++s) {
    printf("%c  ", 'A' + s);
    for (int i = 0; i < m; ++i)
      printf(" %c", 'A' + p->move[i]);
    putchar('\n');
  }
}

void clear() {
  freeEdge(E);
  freeNode(D);
  free(S);
  free(I);
}

int main(int argc, const char *argv[]) {
  readnfa();
  calcdfa();
  if (argc > 1) {
    shownfa();
    showdfa();
    putchar('\n');
  }
  putdfa();
  clear();
  return 0;
}

编译/使用:

gcc nfa2dfa.c -o a.exe
a.exe < nfa.txt > dfa.txt
a.exe --digraph < nfa.txt

其中 nfa.txt 的格式为

n m i1 i2 .. _ <- this '_' is reserved
s1  m1 m2 .. m_
...
sn  m1 m2 .. m_

意思是: n 个状态，m 个输入，紧跟着 m 个输入（单字符）和一个下划线（意思是“空输入”）；接下来 n 行，开头是状态的名字（单字符)，接着以空格分隔表示对应输入下转移到的新状态，没有转移则留一个下划线。
例如，

3 2   0 1 _
0   0,1 0 _
1     2 _ _
2     _ _ _

表示这样一个 NFA 图:

输入本程序后，它会输出一个类似的 DFA 表，如上例会输出

3 2 0 1
A   B A
B   C A
C   C A

表示这样一个 DFA 图:

调用程序时多给一个参数就会输出 dot 可以识别的绘图代码，可以直接粘贴进 https://dreampuf.github.io/GraphvizOnline 生成对应图片
下面给几个示例输入输出:
输入

5 2 0 1 _
0   3 2 _
1   4 _ _
2   _ 3 _
3   3 4 _
4   _ _ _

输出

5 2 0 1
A   B C
B   B D
C   E B
D   E E
E   E E

输入

10 2 a b _
0    _ _ 1,7
1    _ _ 2,4
2    3 _ _
3    _ _ 6
4    _ 5 _
5    _ _ 6
6    _ _ 1,7
7    8 _ _
8    _ 9 _
9    _ _ _

输出

4 2 a b
A   B C
B   B D
C   B C
D   B C