NFA에서 DFA 질문
https://stackoverflow.com/questions/2021890
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
첫째, 이것은 알고리즘이 NFA를 DFA로 변환하도록 요구하는 질문이 아닙니다.
NFA의 동등한 DFA가 최대 2를 가지고 있음으로 알려져 있습니다.N 주, 대부분의 경우에도 NFA와 동일한 수의 상태를 가질 것입니다.
NFA와 동등한 DFA가 가질 상태의 수에 대한 추정치를 어떻게 예측할 수 있습니까? 특정 유형의 NFA는 2 개를 갖기 위해 동등한 DFA가 필요합니다.N 주?
이것을 물어 보는 나의 이유는 최소화를 고려하지 않고 확실히 생산할 NFA를 "발명"할 수 있기 때문에 2N - 1 상태와 "죽은 상태".
해결책
상태의 수는 폭발합니다 비 결정주의, 이것이 귀하의 질문의 열쇠입니다.
각 전환이 고유하게 결정되는 NFA를 복용하면 결정 론적 NFA가되면 정상적인 DFA 일뿐입니다. 그러나 두 번의 전환이 가능한 상태가 있으면 DFA와 다릅니다.
변환 알고리즘을 고려하고 상태와 동일한 레이블로 두 개 이상의 전환이있는 경우 어떻게되는지 살펴보십시오. 여기에는 국가 세트에 해당하는 새로운 상태가 필요합니다.
따라서 문제는 이러한 슈퍼 세트 상태 중 몇 개가 실제로 도달 할 수 있는지 알아내는 데 따릅니다. 물론 이에 대한 멋진 알고리즘을 발명 할 수 있지만 올바른 숫자를 얻으려면 정상 변환 알고리즘을 실행하고 도달 할 수없는 상태를 제거하십시오.
동등한 DFA가 2^N 상태를 갖는 N 상태를 가진 NFA의 경우, 비 결정수를 악용하는 것에 대해 생각합니다. 첫 번째 아이디어는 모든 전환에 동일하게 레이블을 지정하는 것입니다. 그러나 너무 잘 작동하지 않습니다. 대신 각각의 레이블로 모든 주 하위 집합에 도달 할 수 있어야한다는 것을 기억하십시오.
시작 상태를 계산하지 않으면 다음 구성을 수행 할 수 있습니다. N 노드를 작성하고 각각 2^n 세트마다 고유 한 레이블을 생성하고 NFA에서 해당 세트의 각 노드 로이 레이블로 전환을 추가하십시오. 이것은 당신에게 n +1 상태 (1 1은 시작 상태)를 갖는 NFA를 제공하며, 여기서 DFA는 2^n +1 상태가 필요합니다. 물론 최소화 후 2^N DFA 상태를 원한다면 까다로워집니다.
다른 팁
자, n-> n이라고 가정하여 시작하십시오. 이제 한 상태에서 X 다른 상태에서 끝날 수있는 모든 비 결정적 전환에 대해 추정치에 x를 곱하십시오. 이중 수는 정확하지 않을 수 있습니다. 그러나 그것은 당신에게 상한을 주어야합니다.
그러나 해당 DFA를 구축 한 다음 상태를 계산하는 유일한 확실한 방법입니다.
마지막으로, 당신은 아마도 일부 DFA (및 그 문제에 대한 NFA)를 단순화 할 수 있지만 이것은 완전히 새로운 이야기입니다 ...
Start State S 및 Final State N과 함께 N의 함수로 사용 하여이 NFA A(N):
S a-> S
S b-> S
S a-> 0 // NOTE: only "a" allows you to leave state S
0 a-> 1
0 b-> 1
1 a-> 2
1 b-> 2
...
N-1 a-> N
N-2 b-> N
N
이것이 모든 문자열을 받아들이는 것이 분명해야합니다. [ab]* 누가 NTH-From-Trall 편지입니다 a.
의 결정 A(N) 이전 N-1 문자를 기억해야합니다. a, 문자열이 예기치 않게 끝나면, 당신은 a n 편지 전).
이것이 당신이 원하는 상태의 수를 정확히 쳤는지 확실하지 않지만 적어도 2의 계수 내에 있습니다. {0,...,N} 가능하지만 항상 안에 있습니다 S. 이것은해야합니다 2^(N+1) 주, 그러나 A(N) 가졌다 N+2 주.
Jonathan Graehl의 훌륭한 답변을 더욱 확장합니다.
각 상태에 추가하십시오 0, 1, ..., N 의 A(N) 셀프 루프 라벨 c, 즉, 다음 전환을 추가합니다.
0 c-> 0
1 c-> 1
...
N c-> N
그런 다음 가정합니다 c 불을 피우지 않으면 DFA에는 동일하게 포함됩니다 2^(N+1) 조나단의 DFA 상태. 그러나 언제든지 c 상태에서 관찰됩니다 {S,j,k,...,z} <> {S} 우리는 주에 도달합니다 {j,k,...,z}. 따라서 모든 서브 세트 {S,0,...,N} 빈 세트와 DFA는 2^(N+2)-1 상태 A(N) 가지다 N+2 주.
