스크립트에서 RegEx를 사용하여 DFA (Deterministic Finite Automaton)의 상태 다이어그램을 찾았으나이 다이어그램은 설명이없는 예제 일뿐입니다. 그래서 DFA 상태 다이어그램에서 RegEx를 직접 가져 오려고 시도했으며 표현식은 ab+a+b(a*b)*입니다. 나는 원본 RegEx (ab+a*)+ab+가 원본에서 언급 된 얻는 방법 이해하지 않는다. 여기 내 유도 :상태 다이어그램에서 RegEx을 유도하는 방법은 무엇입니까?
내가 어떤 도움, 링크, 참조 및 힌트 감사!
여기에서 정규 표현식을 올바르게 파생 시켰습니다. ab+a+b(a*b)*의 표현식은 (ab+a*)+ab+과 같습니다. DFA 상태 제거를 완료하면 (시작 상태에서 수락 상태로 단일 전환 됨) 더 이상 유도 할 수 없습니다. 그러나 주를 제거하는 순서에 따라 다른 최종 정규 표현식을 얻을 수도 있습니다. 또한 제거가 올바르게 수행되었다고 가정하면 모두 유효해야합니다. 상태 제거 방법은 특정 DFA에 대해 동일한 모든 정규 표현식을 생성 할 수 있다고 보장 할 수 없으므로 원래 정규식에 정확히 도달하지 않아도됩니다. check the equivalence of two regular expressions here하실 수 있습니다.
이 DFA가 원래 정규식 (ab+a*)+ab+과 동일하다는 것을 보여주기위한 특정 사례의 경우,이 상태의 DFA (위의 두 번째 단계와 세 번째 단계 사이)를 살펴보십시오.
(ab+a*)(ab+a*)*ab+ 우리의 표현
(ab+a*)+ab+을 확장하자. 따라서 DFA에서 첫 번째
(ab+a*)은 상태 0에서 상태 2와 상태 3 사이의 중간 지점 (
a* :
a*a)으로 연결됩니다.
다음 부분은 (ab+a*)*이며 (ab+a*)은 0 개 이상 허용됩니다. 0 개의 사본이있는 경우 ab+으로 끝나면 a*a 전환 2 ~ 3의 후반에서 a, 3에서 4로 전환하면 b이되며 상태 4에서 우리는 착륙하고 있습니다. 우리는 자기 루프를 가지고 우리가 원하는만큼 많은 b을 읽을 수 있습니다.
a*a 전이 후반에서
a 및 3-4 천이에서
b 판독
(ab+a*)의 하나 개 이상의 사본을 갖는다.
a*은 상태 4의
a*ab 자체 루프의 전반부에서 가져오고 두 번째 절반 인
ab은 정규식의
ab+의 마지막이거나
(ab+a*)의 다른 사본입니다. 정확하게 표현식이
(ab+a*)+ab+에 도달하는 상태 제거가 있는지는 확실하지 않지만, 그게 가치있는 일인가? 당신은이 DFA의 구조를 더 명확하게 포착 한 정규 표현식을 생각합니다.
후속 다이어그램은 서로 '단순화'되어 있다는 것을 알고 있습니까? 어떤 단계를 밟았습니까? – xtofl
맨 위에있는 첫 번째 만 주어진다. 나는 마지막 세 개를 만들었다. 그렇다.) 마지막으로 붙어있다. ab + a + b에서 (ab + a *) + ab + (a * b) *'? – PatrickSteiner