방금 계산 이론에 대해 읽기 시작했습니다. 어느 것이 더 강력한 지 (문자열 수용에서) 비교하면 둘 다 동일합니다. 그러나 효율성은 어떻습니까? DFA는 나가는 가장자리가 하나 뿐이며 모호성이 없으므로 NFA에 비해 빠릅니다. 그러나 NFA의 경우 가능한 모든 사례를 확인해야하며 시간이 오래 걸립니다. DFA가 NFA보다 더 효율적이라고 말할 수 있습니까?
그러나 뇌의 다른 부분은 NFA가 이론에만 존재한다고 생각하므로 DFA와 효율성을 비교할 수 없습니다.
답변
효율적인 정의 방법에 따라 두 가지 답변이 있습니다.
표현의 소형화
적은 비용으로 더 많은 것을 말하십시오 : NFA가 더 효율적입니다.
DFA를 NFA로 변환하는 것은 간단하며 표현의 크기를 늘리지 않습니다.
그러나 가장 작은 DFA가 가장 작은 NFA보다 기하 급수적으로 큰 정규 언어가 있습니다. 전형적인 예이다 에 대한 K 고정.
(a|b)∗b(a|b)kk
계산
빠른 실행 : DFA가 더 효율적입니다.
오늘날 사용하는 컴퓨터는 본질적으로 결정 론적입니다. 그것은 비결정론을 다루는 데 나쁜 영향을 미친다. NFA를 결정적으로 처리하는 두 가지 일반적인 방법이 있습니다. 한쪽의 역 추적, 다소 비용이 많이 들거나 활성 상태를 추적하는 것입니다. 즉, 각 전환이 최대 배 더 오래 걸립니다 (여기서 N 은 NFA의 크기 임) .
NN
답변
n
2n
DFA 일치는 입력 문자열 크기에서 선형입니다. NFA 일치에는 역 추적이 포함되므로 NFA가 더 많은 작업을 수행합니다. 따라서 DFA가 더 효율적입니다.
답변
위의 답변에 추가하기 만하면됩니다.
NFA 는 병렬 프로세서에서 시뮬레이션 할 수 있다는 점에서 DFA보다 계산 효율성이 더 뛰어납니다.
BTW : 사람들은 NFA가 실제로 존재할 수 없다고 말하는 것을 봅니다. 나는달라고 간청한다. 프로세서 수가 많은 컴퓨터는 많은 작업을 병렬로 실행할 수 있으며 비 결정적 시스템으로 간주 될 수 있습니다. 계산의 각 분기를 새 프로세서에 할당하고 수락 할 때마다 모두 중지 할 수 있습니다.
답변
ϵ
답변
다른 사람들이 지적했듯이 “효율”의 의미를 정의해야합니다. 이것을 설명하기 위해 나는 다른 대답으로 합리적인 모델을 제시합니다.
특히 실제 머신에서 어떻게 구현할 것인지를 무시하고있는 오토 마톤 모델 만 살펴보면 명백한 효율 측정은 “(가장 짧은) 실행에서 수행 된 전환 수”입니다.
ε
답변
기술적으로 NFA는 비결정론을 사용할 필요가 없기 때문에 DFA보다 일반적인 개념입니다. 다시 말해 모든 DFA는 NFA입니다. 이러한 관점에서 모든 언어에 대해 가장 효율적인 DFA만큼 효율적인 NFA가 있습니다.
이것 외에는 Raphael에 동의하는데, 그것은 효율성 과 구현에 대한 의미가 매우 중요하다는 데 동의합니다 .
답변
우리가 알고있는 Automata, 즉 사람의 힘이나 사람의 직접적인 참여없이 어떤 행동을 수행 할 수있는 기계. 예 : 세탁기. 유한 오토마타는 1 프레스 ON 2 프레스 OFF와 같은 기계로 작업을 수행하는 상태를 알고 있으므로 유한 오토마타라고하는 2 가지 상태 만 있습니다. 이제 결정 론적 유한 오토마타와 같은 DFA로 오십시오. 공식적으로는 모호성이없는 상태를 쉽게 확인할 수 있으며 비공식적으로 1 개의 심볼에 1 개의 전환 만 허용하면됩니다. NFA : 비 결정적 유한 오토마타. 실제 상태를 계산하는 데 더 많은 시간이 필요하며 모호성이 있으며 비공식적으로 1 개의 심볼에 여러 개의 허용되는 전환이 있다고 말합니다. 대상에 도달하는 데 시간이 걸리는 경우 NFA는 DFA보다 시간이 더 걸리지 만 NFA는 DFA보다 더 많은 데이터를로드 할 수 있습니다. * DFA와 NFA는 문자열을 인식하는 능력이 동일합니다. 감사합니다 .. Deepali kaushik