CS 클래스에 McNaughton-Yamada 알고리즘을 사용하여 DFA를 생성해야합니다. 문제는 알고리즘이 보충 자료이며 정확하게 무엇인지 명확하지 않다는 것입니다. RegEx가 지정된 DFA를 찾는 방법입니까, DFA plus를 최소화하는 방법입니까? 주제에 대한 정보를 찾을 수없는 것 같습니다.McNaughton-Yamada 알고리즘이란 무엇입니까?
클래스의 DFA가 우리의 book에 설명 된 '표시'최소화와 다른 것으로 보이지 않으면 강사가 보여준 최소화 루틴이 표시되기 때문에 혼란 스럽습니다. 답장을 보내
감사합니다,
나단
"... McNaughton-Yamada 분석 알고리즘을 사용하면 전환 테이블이 지정된 유한 상태 시스템에서 허용하는 단어를 설명하는 정규 표현식을 찾을 수 있습니다. 수정되지 않은 알고리즘은 n- 상태 시스템을 나타내는 4n 항을 생성합니다. 중복 계산을 제거하고 동일한 상태 다이어그램에서 가능한 경로에 해당하지 않는 상위 수준 표현식을 거부하면이 수를 줄일 수 있습니다. 빈 표현식과 null 단어는 알고리즘에 의해 자유롭게 생성되므로 나머지 표현식은 심각한 단순화 문제를 나타냅니다. "
; 그들은 Thompson의 버전을 보여 주며 McNaughton-Yamada 알고리즘은 기본적으로 동일하지만 정규 표현식에서 직접 DFA를 생성한다고 주장합니다.
은 그들의 알고리즘은 일반적으로 톰슨의 작품에서 별도의 제기하지 않습니다. Thompson의 원본은 정규 표현식에서 시뮬레이션 된 NFA로 이동했습니다. Thompson-McNaughton-Yamada 알고리즘은 과도 시뮬레이션과 달리 정규 표현식을 메모리에 저장된 실제 NFA로 바꾸는 확장입니다.
NFA를 DFA (변환)로 변환하는 것은 McNaughton 또는 Yamada의 확장 물이 아닙니다. 오히려 subset construction (일명 powerset 생성) 알고리즘을 통해 이루어집니다.
컴파일러 구축 툴킷의 regular expression to NFA and DFA 도구를 사용하면 Thompson-McNaughton-Yamada 알고리즘과 하위 세트 생성 알고리즘이 임의의 정규 표현식에서 작동하는 것을 볼 수 있습니다.