DFA, NFA 및 엡실론 NFA를 사용하면 특정 정규 언어를 대표 할 수 있습니다. 이러한 표현 중 하나를 사용하여 동일한 정규 표현식에 도달 할 수 있는데, 왜 유한 오토마타의 세 가지 표현 방식을 모두 연구해야합니까? DFA가 할 수없는 NFA가 무엇을 할 수 있는지에 대한 설명이있을 수 있습니다. 즉 NFA는 불확실성 설계에 도움이 될 수 있습니다. 예를 들어 게임 (체스)을 디자인 할 때 NFA를 사용하여 쉽게 표현할 수있는 특정 위치에서 특정 조각을 이동하는 많은 옵션이 있습니다. 그러나 NFA 또는 DFA를 사용하여 동일한 작업을 수행 할 수있는 경우 엡실론 NFA는 어떻게 사용됩니까?
답변
네 번째 정규 문법을 추가하십시오. 다른 사람들이 있습니다 …
DFA + NFA에 대한 관심의 일부는 간단한 계산 모델이며 NFA (및 -NFA) 비결정론의 예 (보다 정교한 모델의 중요한 아이디어)입니다. DFA와 NFA가 동일한 언어 집합을 수용 함을 증명하기 위해 단순하고 이해하기 쉬운 설정에서 매우 중요한 현상을 탐색하고 있습니다.
ϵ정규 표현식 (및 정규 문법)은 완전히 다른 형식이며 동일한 언어 집합을 설명합니다. 다시 말하지만,이 사실의 증거는 중요한 상호 관계를 탐구하며 형식주의가 매우 다른 것처럼 보일 수 있고 근본적으로 다른 개념을 기반으로하지만 동일한 언어를 설명하는 예입니다. 다시 말하지만 다소 간단한 설정입니다.
“실제”사용의 경우 정규식으로 시작하여 고성능 검색을위한 최소 DFA를 얻을 수 있습니다. 디지털 회로는 본질적으로 DFA이므로 컴퓨터 공학의 핵심 요소임을 이해해야합니다. 마지막으로, 시스템이 실제 DFA와 매우 거리가 멀어도 시스템을 이해하는 데 도움이 될 수 있더라도 시스템은 종종 외부 자극에서 “상태에있는”상태로 “다른 시스템으로 이동”하는 것으로 모델링 될 수 있습니다.
나중에 추가됨 : Raphael에서 언급했듯이 DFA를 만드는 데 많은 비용이 들고 NFA가 훨씬 작기 때문에 검색을 위해 NFA를 직접 해석하는 것이 더 효율적일 수 있습니다.
답변
DFA와 NFA의 다양한 형식 / 대응을 연구해야하는 이유는 매우 다양합니다. 다음은 고급 복잡성 이론에서 일부 선택된 주요 내용입니다.
-
NFA는 “병렬 계산”에 대한 흥미로운 모델입니다. NFA를 통한 상태의 발전은 병렬 버전의 DFA 계산으로 간주 할 수 있습니다. 따라서 DFA와 NFA 계산은 순차적 계산과 병렬 계산의 차이점을 반영합니다. 두 컨텍스트를 비교함으로써 문제의 고유 한 알고리즘 복잡성을 연구하는 데 도움이됩니다.
-
NFA는 종종 정규 표현식 일치 시스템 (유닉스 시대에 생성 된 최신 언어의 유비쿼터스)에서 주로 사용되며, 일반적으로 NFA로 변환 된 정규 표현식에 대한 설명을 허용 한 다음 DFA로 변환하여보다 효율적인 검색을 지원합니다.
-
이 영역에 남아있는 몇 가지 공개 된 문제가 있으며 종종 DFA / NFA 서신을 바탕으로 연구됩니다. 예를 들어 DFA (cstheory stackexchange) 에 열려있는 문제가 있습니까?를 참조하십시오 . 놀랍게도, 그들 중 일부는 P 대 NP 문제, 즉 DFA의 교차 비 지속성을 포함하여 CS의 매우 깊은 영역에 묶여 있습니다. 또 다른 열린 영역은 예를 들어 DFA에 대한 최소 NFA를 계산하는 것 입니다.
-
또한 일부 관련 통찰력에이 semifamous / highvoted 질문을 참조 cstheory.se : 깨달음은 내가 유한 오토마타를 공부 한 후 달성하는데있어 무엇을?
-
DFA와 NFA의 적용 범위는 매우 다양하며, 둘 사이의 대응 관계가 종종 활용됩니다. 문자열 패턴 일치는 위에서 언급되었지만 DFA / NFA 구성은 (자동화 된) 음성 인식에 자주 사용됩니다. 예를 들어이 인용 된 논문 : 음성 인식의 가중 유한 유한 상태 변환기 / Mohri, Pereira, Riley
답변
DFA는 다음 상태가 함수에 의해 결정되므로 NFA보다 구현이 더 쉽고 NFA는 NFA가 여러 경로 중에서 선택할 수 있기 때문에 사용자가 원하는 것을 출력으로 쉽게 표현할 수 있도록 도와줍니다. epsilon-NFA는 입력 심볼을 사용하지 않고 전환을 수행 할 수있는 NFA의 확장입니다.
답변
DFA의 주 수에는 불쾌한 것이 있습니다. 때때로 폭발 합니다 .
간단히 말해서, 주 수가 너무 많으면 (아직 유한하지만 우리는 실제 세계에 살고 있습니다), 약간의 속도 저하로 인한 복잡성에 대처하기 위해 추상화 수준을 높여야합니다. NFA 및 AFA와 같은 다른 모델은 일반 언어를 표현하는보다 간결한 방법을 제공해야합니다.