전이 표에서 정규 표현식을 생성하는 프로그램

Question

유한 자동화가 주어진 정규 표현식을 생성하는 프로그램을 작성하는 방법이나 c (선호)에있는 프로그램이있는 경우 누구라도 궁금합니다.

상황을 덜 복잡하게 만들려면 FA가 최소 형식이고 FA에 FinalState가 하나만 있고 StartState가 하나만 있다고 가정하고 상태 수를 약 4로 제한하고 싶습니다.

필자는 잠시 동안 생각해 봤는데, 가장 먼저해야 할 일은 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))

필자는 시간 동안 내 머리를 고문하고

하지만, 이 문제를 어떻게 해결할 지 잘 모르겠다. 어떤 아이디어라도 대단히 감사하겠습니다.

Answer 1

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; 
} 

Answer 2

클레 네의 알고리즘 (Floyd-Warshall 알고리즘의 특수한 경우)으로이 작업을 수행 할 수 있습니다. http://libalf.informatik.rwth-aachen.de/index.php?page=download