DFA와 비교했을 때의 NFA의 장점/단점

Question

비교했을 때 DFA와 NFA의 상대적인 장점과 단점은 무엇입니까?

DFA는 NFA보다 구현하기가 쉽고 NFA는 DFA보다 수락 상태에 도달하는 것이 더 느리지 만 다른 명확하고 잘 알려진 장점/단점이 있습니까?

Answer 1

DFA를 통한 NFA의 장점은 항상 "올바른 경로 선택"이라는 속성입니다. "적절한 경로 선택"알고리즘에서는 NFA에서 DFA 로의 변환이 일반적으로 작동하므로 여러 NFA 상태를 상징하는 DFA 상태가 생성됩니다. 따라서 귀하의 NFA가 주 A에 있고 A, B 또는 C로 갈 선택권이있는 경우 DFA의 다음 상태는 {A, B, C}가됩니다.

이점과 단점을 설명합니다. DFA는 다음 상태가 함수에 의해 결정되므로 더 쉽게 구현할 수 있습니다. NFA를 사용하면 사용자가 원하는 것을 쉽게 표현할 수 있습니다. NFA가 여러 경로 중에서 선택할 수 있기 때문입니다.

Answer 2

NFA 및 DFA는 동일한 언어 집합 (일반 언어)을 허용합니다.

NFA (DFA는 NFA의 하위 집합이므로 DFA가 아니기 때문에)를 직접 구현하면 일반적으로 역 추적을 허용하지만 DFA를 직접 구현하려면 입력 길이만큼 많은 단계 만 필요하므로 그 의미에서 , DFA는 "동등한 NFA (DFA가 아닌)보다 빠릅니다.

주어진 언어 또는 RE (예 : 알고리즘)에 해당하는 FA를 찾으려는 경우 규칙이 덜 엄격하기 때문에 NFA에 먼저 도착하는 것이 일반적으로 더 쉽습니다. 이것은 FA의 존재를 입증하려고 시도 할 때 특히 그렇습니다. 왜냐하면 NFA의 존재는 DFA의 존재만큼이나 우수하기 때문입니다. DFA가 필요한 경우 알고리즘은 (a) NFA를 동등한 DFA로 변환하고 (b) DFA를 최소화하기위한 알고리즘이 있습니다.

총체적인 일반화를 수행하면 DFA는 더 빠르지 만 (상태 및 전환 수의 측면에서) 더 복잡하지만 NFA는 더 느리지 만보다 간단합니다 (동일한 용어로).

Answer 3

DFA와 비교하여 NFA의 확실한 이점 중 하나는 NFA를 사용하여 두 개 이상의 언어의 결합, 교차, concetanation 등의 언어를 나타내는 FA를 쉽게 만들 수 있다는 것입니다. 말하자면, 당신이 약간 간단한 FA가 일의 부분을하는 경우에, 당신은 NFA를 사용하여 그 (것)들을 쉽게 결합 할 수있다. DFA를 사용하는 동안 모든 작업을 자체적으로 수행하는 새 자동 생성 기능을 구축해야합니다.

참조하십시오. 구현하기가 더 쉽습니다. 하지만 언급 한 시간 문제가 있습니다.