3
Google을 검색했으며 많은 페이지에서 최소화 된 DFA 상태 또는 트랩 상태가 제거되었습니다. 내 질문은 일부 전환이 정의되지 않은 경우 어떻게 여전히 DFA 수 있습니다. 그래서 사람들이 뭐라고하니?Dead 상태가 Minimized DFA에 포함되어 있습니까?
A
답변
6
심지어 최소한의 DFA에는 죽은 상태가 포함되어야합니다. 그렇지 않으면 그들은 (a) DFA가 아니거나 (b) 최소가 아닌 다른 언어와 동일한 언어를 허용하지 않습니다. 예를 들어, 알파벳 {a, b} 이상의 언어 {a}에 대한 최소 DFA는 다음과 같은 3 가지 상태 여야합니다. a를 볼 수 있고 받아 들일 수있는 시작 상태. 당신이 다른 것을 본다면 거절하는 수락 국가; 그리고 수락하는 국가에있는 b 또는 무엇이라도 보게되면 죽은 상태가됩니다.
최소의 DFA에서 사각 지대를 생략 한 적이 없습니다. 신성 모독!
0
죽은 상태는 '최소'버전에서 제거되지 않지만 예 그들은 (아마 당신이 용어가 섞여있어) DFAS의 '반전'
0
@PrashantBhardwaj 동안 손실됩니다 : 나는 또한 그 (죽은 생각 상태 및 해당 죽은 동작)이 포함되어야합니다. DFA를 완료하는 것이 포함되므로 최소화 된 DFA에서 특정 상태에 대한 익명 이동을 고려하지 않기 때문입니다.
그래도 질문에 대한 답변이 없습니까? 마지막으로, 우리는 그것을 포함 할 것인가 말 것인가? 누구든지 그것을 증명할 수 있습니까?
+0
"결정 론적 유한 상태 기계 (deterministic finite state machine)는 유한 상태 문자열을 허용/거부하고 각 입력 문자열 **에 대해 자동화의 고유 한 계산 (또는 실행)만을 생성하는 유한 상태 기계입니다. ** 출처 ** : DFA의 위키 백과. 특정 이동이 정의되지 않은 경우, 이것만으로도 작동 불능 상태가 포함될 수 있습니다. 포함되지 않은 경우 DFA라고하는 것이 합당합니까? – user2925949
[페이지] (http://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/min-fa.html)을보십시오. 이 죽은 상태에 따르면 DFA에서 제거됩니다. –
@PrashantBhardwaj 그건 이상하고 이상하며 이상한 규칙입니다. 하나는 최소한의 DFA라고 부르는 것이므로 NFA (DFA는 "충돌"할 수 없음)를 호출합니다. 둘째, Myhill-Nerode 정리와 정의가 다릅니다. 올드 도미니언 대학교 (Old Dominion University)의 코스 노트를 유일한 참고 자료로 사용하지 않겠습니다. MIT, Harvard, Oxford, Yale, Stanford, Cambridge 등은이 문제에 관해 무엇을 말해야합니까? 어쨌든 최소한의 DFA만으로는 단일 죽은 상태가 필요합니다 ... 왜 이것을 제거 할 것인지 확신 할 수 없습니다. 기괴한. – Patrick87
그래서 NFA라고 부릅니다. 또한 UIUC의 계산 이론 강의 노트를 검색했습니다. 죽은 상태를 제거하는 방법은 없습니다. 그러나 이것들은 내가 만난 몇 개의 링크입니다. [링크 1 (www.cs.fsu.edu/~whalley/cop5621/chap3.handout.pdf) [Link2부터 (en.wikipedia.org/wiki/DFA_minimization) [LINK3 (code.google .com/p/regex /) 실제로 일부 컴파일러 책에서는 제공되었습니다. –