나는이 책을 읽고있다 : 계산 이론을 소개하고이 예제를 고수했다.DFA를 정규 표현식으로 변환하는 방법은 무엇입니까?
DFA를 먼저 GNFA (일반 비 결정적 유한 자동 오토마타)로 변환 한 다음 GNFA를 정규 표현식으로 변환하여 해당 표현식으로 변환하십시오. 여기
은 예입니다 enter image description here나는 네 번째 상태에 도달하기 위해 반복적으로 이것을 사용한다 : enter image description here
불행하게도, 나는 C에 B에서 무슨 일이 일어나고 있는지 이해할 수 없다? 나는 우리가 상태 2를 없애려고한다는 것을 이해하지만, 어떻게 b에서 c에 도착 하는가?
대단히 감사합니다!
이것은 처음에는 매우 까다로운 일일 수 있지만 정의 1.64를 확인하고 더 많은 정리를 위해 CONVERT (G) 함수를 볼 것을 제안합니다. 그러나 각각의 가능한 이웃 상태의 함수를 사용하여 간단한 설명과 같이 A와 B에서
첫째, 시작 상태를 추가하고 새로운 상태를 동의;
이후 qrip가 제거 된 후에 각각의 새 경로를 계산해야합니다.이 경우에는 상태 1입니다.
그래서 처음부터 q2까지, 당신은 단지 엡실론과 a에서 레이블 a 만 얻습니다.
동일은 시작에서 q3까지이며, 결과는 b입니다.
이제 q2에서 q2로가는 qrip에 대해 q라는 라벨을 지정하고 a로 라벨을 달아 돌아 오면 aa U b를 얻을 수 있습니다.
qame을 통해 q3에서 q3으로 이동하므로 bb에서 결과가 q3에 루프가 없다는 것을 알 수 있습니다.
qrip을 통해 q2에서 q3까지 이제는 ab 라벨을 결합한 a와 b 만 연결하면됩니다.
마지막으로 qrip을 통과하는 q3에서 q2까지 연결하고 b와 a를 연결하지만 이번에는 q3과 q2 사이의 이전 경로와 결합을 만듭니다.
이제 새 qrip을 선택하고 동일한 알고리즘을 다시 수행하십시오.
