1

我很好奇是否有人知道如何编写程序以在给定有限自动化的情况下生成正则表达式，或者是否已经存在任何程序（最好在 c 中）。

为了让事情变得不那么复杂，我想将状态数限制在 4 个左右，假设 FA 是最小形式，并且 FA 只有一个 FinalState 和一个 StartState。

我已经考虑了一段时间，我认为要做的第一件事就是为 FA 创建一个转换表。

所以FA可能看起来像这样：

NumberOfStates 4 
StartState   1 
FinalState   4 
StateNumber  NextStateA   NextStateB
1            2            4
2            3            2
3            4            4

这将生成正则表达式： b + (ab*a(a + b))

我已经绞尽脑汁好几个小时了，但我不知道如何去做。非常感谢任何想法。

4

2 回答 2

3

以下是实现 (a+b+c)*abc 的 FA 的代码。但我无法理解其中的逻辑。

int main()
{
     char str[50],input[15],inpstate[15],outstate[15],state='A';
     int i=0,j;
     strcpy(input,"abcabcabcabc");
     strcpy(inpstate,"AAABBBCCCDDD");
     strcpy(outstate,"BAABCABADBAA");
     printf("\nEnter the string:-  ");
     gets(str);
     while(str[i]!='\0')
     {
          for(j=0;j<12;j++){
         if(inpstate[j]==state && input[j]==str[i]){
              state=outstate[j];
              break;
          }
           }
          if(j==12){
          state='E';
          break;
        }
        i++;
     }
     if(state=='D')
          printf("\nValid String \n");
     else
          printf("\nInvalid String \n"); 
     return 0;
}
于 2012-11-25T09:41:39.930 回答
1

您可以使用 Kleene 算法（这是 Floyd–Warshall 算法的一个特例）来做到这一点。

您会发现这已实现，例如，在 libAMoRE 库中：http ://libalf.informatik.rwth-aachen.de/index.php?page=download

于 2013-01-17T20:00:11.157 回答