1

有限のオートメーションを指定して正規表現を生成するプログラムを作成する方法を誰かが知っているか、またはプログラム (できれば c) が既に存在するかどうかに興味があります。

物事を簡単にするために、状態の数を約 4 に制限したいと思います。FA は最小形式であり、FA には 1 つの FinalState と 1 つの 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

Follwoingは、（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 に答える