DFA 최소화

DFA의 예.상태 $c{\displaystyle }$ ${\displaystyle c}$에 있는 경우$,$ $상태{\displaystyle }$ d {\$displaystyle$d} $또는{\displaystyle }$상태$$e {\$displaystyle$ e$}$과(와) 모든 입력 문자열에 대해 동일한 동작을 나타낸다$.$ $마찬가지$로 상태 a$${\$displaystyle$ a$}$과 b ${\disclaystyle b}$은(와)가$$ 구분되지 않는다.DFA는 연락이 불가능한 주가 없다.

등가 최소 DFA.구분이 안 되는 주들이 하나로 합쳐졌다.

오토마타 이론(이론적 컴퓨터 과학의 한 분야)에서 DFA 최소화는 주어진 결정론적 유한 자동화(DFA)를 최소 상태 수를 갖는 등가 DFA로 변환하는 작업이다.여기서 두 개의 DFA가 동일한 정규어를 인식하면 등가라고 부른다.이 과제를 달성하는 몇 가지 다른 알고리즘이 알려져 있고 오토마타 이론에 관한 표준 교과서에 기술되어 있다.^[1]

최소 DFA

각 정규 언어의 경우, 최소 상태 수를 갖는 DFA를 받아들이는 최소 자동화가 존재하며, 이 DFA는 고유하다(주들이 다른 이름을 부여받을 수 있다는 점을 제외).^[2][3]최소한의 DFA는 패턴 매칭과 같은 작업에 최소한의 계산 비용을 보장한다.

원래 DFA가 수용하는 언어에 영향을 주지 않고 원래 DFA에서 제거하거나 병합할 수 있는 두 가지 등급의 주가 있다.

• 연결할 수 없는 상태는 입력 문자열의 DFA 초기 상태에서 도달할 수 없는 상태를 말한다.이 주들은 제거될 수 있다.
• 죽은 주는 최종 상태에 도달할 수 없는 주이다.이러한 상태는 자동화가 완료되어야 할 필요가 없는 한 제거될 수 있다.
• 구분되지 않는 상태는 입력 문자열에서 서로 구분할 수 없는 상태를 의미한다.이 주들은 합병될 수 있다.

DFA 최소화는 보통 다음 세 단계로 수행된다.

1. 사망 및 도달할 수 없는 상태를 제거한다(이러하면 다음 단계가 가속화됨).
2. 불분명한 주(州)를 병합해서
3. 선택적으로, 결과 DFA를 완료해야 하는 경우 단일 정지 상태("싱크" 상태)를 다시 생성하십시오.

연결할 수 없는 상태

이 절은 출처를 인용하지 않는다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션을 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다.(2020년 9월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

The state ${\displaystyle p}$ of a deterministic finite automaton ${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}$ is unreachable if no string ${\displaystyle w}$ in ${\displaystyle \Sigma ^{*}}$ exists for which ${\displaystyle p=\delta ^{*}(q_{0},w$$)}$. In this definition, ${\displaystyle Q}$ is the set of states, ${\displaystyle \Sigma }$ is the set of input symbols, ${\displaystyle \delta }$ is the transition function (mapping a state and an input symbol to a set of states), ${\displaystyle \delta ^{*}}$is its extension to strings (aka extended transition 함수), ${\displaystyle {q\mathrm{}}_{}}$ 0 ${\$이 초기$$ 상태, $F{\displaystyle }$ ${\displaystyle F}$이(가) 승인(최종) 상태의 집합이다.도달 가능한 상태는 다음 알고리즘으로 얻을 수 있다.

하게 하다 도달할 수 있는_이름 := {q0} 하게 하다 new_new := {q0}  하다 {     임시 변통하다 := 그 텅 빈 세트     을 위해 각각 q 에 new_new 하다         을 위해 각각 c 에 Σ 하다             임시 변통하다 := 임시 변통하다 ∪ {p 그런 저것 p = δ(q,c)}     new_new := 임시 변통하다 \ 도달할 수 있는_이름     도달할 수 있는_이름 := 도달할 수 있는_이름 ∪ new_new } 하는 동안에 (new_new ≠ 그 텅 빈 세트)  연결할 수 없는_불가결한 := Q \ 도달할 수 있는_이름 

세트의 효율적인 구현을 가정한다(예:new_states이 알고리즘은 시간 복잡성 $O{\displaystyle (n}$+ $){\displaystyle O(n+m)}$로 구현할 수 있으며, 여기서 n $\{\backslash$$displaystyle n}$은(는$)$ 상태 수이고 $m{\displaystyle }$ ${\displaystyle m}$은 입력 자동화의 전환 수입니다.

연결할 수 없는 상태는 DFA가 수락하는 언어에 영향을 주지 않고 DFA에서 제거할 수 있다.

구분이 안 되는 상태

다음 알고리즘은 구분이 되지 않는 상태를 병합하기 위한 다양한 접근방식을 제시한다.

홉크로프트 알고리즘

Hopcroft(1971년)로 인해 DFA의 구분이 되지 않는 상태를 병합하기 위한 하나의 알고리즘은 파티션 미세화에 기초하여 DFA 상태를 동작에 의해 그룹으로 분할한다.이러한 그룹은 Myhill-Nerode 동등성 관계의 동등성 클래스를 나타내며, 동일한 파티션의 두 상태가 모든 입력 시퀀스에 대해 동일한 동작을 갖는 경우 모든 상태가 동등하다.즉, 파티션 P 내에서 동일한 동등성 등급에 속하는 두 상태 p와₁ p₂, 그리고 모든 입력 단어 w에 대해 w에 의해 결정된 전환은 항상 상태₁ p와₂ p를 동일한 상태로 가져가야 하며, 상태 p를 모두 인정하는 상태 또는 둘 다 거부하는 상태를 나타내야 한다.w가 p를₁ 수용 상태로 가져가고₂ p를 거부 상태로 가져가는 것이 가능하지 않아야 하며 그 반대의 경우도 가능해야 한다.

다음 가성소드는 쉬에 의해 주어진 알고리즘의 형태를 설명한다.^[4]대체 형태도 제시됐다.^[5][6]

P := {F, Q \ F} W := {F, Q \ F} 하는 동안에 (W 이다 아닌 텅 빈) 하다      고르다 그리고 제거하다 a 세트 A 로부터 W      을 위해 각각 c 에 Σ 하다           하게 하다 X 있다 그 세트 의 미국. 을 위해 어떤 것 a 전이 에 관하여 c 주연들 로 a 주 에 A           을 위해 각각 세트 Y 에 P 을 위해 어떤 것 X ∩ Y 이다 비어 있지 않은 그리고 Y \ X 이다 비어 있지 않은 하다                대체하다 Y 에 P 에 의해 그 두 개 놓다 X ∩ Y 그리고 Y \ X                만일 Y 이다 에 W                     대체하다 Y 에 W 에 의해 그 같은 두 개 놓다                다른                     만일  X ∩ Y  <=  Y \ X                           덧셈을 X ∩ Y 로 W                     다른                          덧셈을 Y \ X 로 W 

알고리즘은 너무 거친 파티션으로 시작한다. Myhill-Nerode 관계에 따라 동일한 상태의 모든 쌍은 파티션의 동일한 집합에 속하지만 불평등한 쌍은 동일한 집합에 속할 수 있다.그것은 점진적으로 더 많은 수의 작은 집합으로 파티션을 재조정하며, 각 단계에서 상태 집합을 반드시 불평등한 하위 집합의 쌍으로 분할한다.초기 분할은 상태를 두 개의 하위 집합으로 분리하는 것으로, 서로 동일한 동작을 가지지 않는 상태, 즉 수용하는 상태와 거부되는 상태를 명확히 나타낸다.그런 다음 알고리즘은 현재 파티션과 입력 기호 c에서 세트 A를 반복적으로 선택하고 파티션의 각 세트를 입력 기호 c에서 A로 이어지는 상태의 부분 집합과 A로 이어지지 않는 상태의 부분 집합, 즉 두 개의 부분 집합(비었을 가능성이 있음)으로 분할한다.A는 이미 다른 파티션 집합과 동작이 다른 것으로 알려져 있기 때문에 A로 이어지는 서브셋도 A로 이어지지 않는 서브셋과는 동작이 다르다.이러한 유형의 스플릿을 더 이상 찾을 수 없으면 알고리즘은 종료된다.

보조정리. 등가 등급 B와 C로 분할되는 고정 문자 c와 등가 등급 Y를 감안할 때 전체 파티션을 세분화하려면 B 또는 C 중 하나만 있으면 된다.^[7]

예:동등성 클래스 B와 C로 분할되는 동등성 클래스 Y가 있다고 가정합시다.클래스 D, E, F, D 및 E에도 문자 C에 B로 전환되는 상태가 있다고 가정해 보십시오. 반면 F에는 문자 C에 C로 전환되는 상태가 있다고 가정해 보십시오.Lemma에 의해, 우리는 B와 C 중 하나를 구분자로 선택할 수 있다, B라고 하자.그리고 나서 D와 E의 상태는 B로 전환됨으로써 분할된다.그러나 B를 가리키지 않는 F는 알고리즘의 현재 반복 중에는 분할되지 않으며 다른 구분자에 의해 정제될 것이다.

관찰.모든 B나 C는 D, E, F와 같은 참조 클래스를 정확하게 나누기 위해 필요하다-- 하위 집합은 그렇지 않을 것이다.

가장 바깥쪽 문장()if Y is in W의 목적은 부랑어 집합체인 W를 패치하는 것이다.우리는 알고리즘의 앞의 문장에서 Y가 방금 분할되었음을 알 수 있다.만약 Y가 W에 있다면, 그것은 향후 반복에서 클래스를 분할하기 위한 수단으로 쓸모없게 되었다.따라서 Y는 위의 관찰로 인해 양쪽 분할로 대체되어야 한다.그러나 Y가 W에 있지 않으면 위의 리마 때문에 둘 다가 아니라 둘 중 하나만 W에 추가하면 된다.두 스플릿 중 작은 스플릿을 선택하면 W에 새로 추가된 것이 Y의 절반 이하라는 것을 보장한다; 이것이 다음 단락에서 설명한 것처럼 Hopcroft 알고리즘의 핵심이다.

이 알고리즘의 최악의 경우 실행 시간은 O(ns log n)이며 여기서 n은 상태 수, s는 알파벳의 크기다.이 바운드는 자동화의 각 ns 전환에 대해 전환의 목표 상태를 포함하는 Q에서 도출된 집합이 둘 이상의 인수에 의해 서로 상대적으로 감소하는 크기를 가지기 때문에 각 전환은 알고리즘의 분할 단계의 O(log n)에 참여한다.파티션 미세화 데이터 구조는 각 분할 단계를 이에 참여하는 전환 횟수에 비례하여 시간 내에 수행할 수 있도록 한다.^[8]이것은 문제를 해결하기 위해 알려진 가장 효율적인 알고리즘으로 남아 있으며, 특정 입력물 분포의 경우 평균 사례 복잡성은 O(n log log n)보다 훨씬 좋다.^[6]

일단 Hopcroft의 알고리즘을 사용하여 입력 DFA 상태를 동등성 등급으로 그룹화하면, 최소 DFA는 각 동등성 등급에 대해 하나의 상태를 형성하여 구성할 수 있다.S가 P의 상태 집합이고, s가 S의 상태이고, c가 입력 문자인 경우, S의 상태, 입력 c의 상태에서 최소 DFA의 전환은 입력 자동화가 입력 c의 상태 s에서 이동하는 상태를 포함하는 세트로 간다.최소 DFA의 초기 상태는 입력 DFA의 초기 상태를 포함하고 있으며, 최소 DFA의 수용 상태는 구성원이 입력 DFA의 상태를 수용하고 있는 상태를 말한다.

무어의 알고리즘

무어의 DFA 최소화 알고리즘은 에드워드 F 때문이다. 무어(1956년).Hopcroft의 알고리즘처럼 수용과 거부 상태를 분리하기 시작하는 파티션을 유지하며, 더 이상의 정밀한 작업이 이루어질 수 없을 때까지 파티션을 반복적으로 재조정한다.각 단계에서 현재 파티션을 s + 1 파티션의 가장 일반적인 정교함으로 대체하며, 그 중 하나는 현재 파티션이고 다른 하나는 각 입력 기호에 대한 전환 기능 하에서 현재 파티션의 사전 이미지들이다.이 교체가 현재 파티션을 변경하지 않으면 알고리즘이 종료된다.최악의 경우 시간 복잡성은 O(ns²)이다. 알고리즘의 각 단계는 동일한 새 파티션 집합의 상태가 연속적으로 순서에 따라 오더되도록 상태를 다시 정렬하기 위해 시간 O(ns)로 수행될 수 있으며, 각 단계부터 마지막 단계까지 파티션의 세트 수를 증가시키기 때문에 최대 n개의 단계가 있다.최악의 경우 동작을 유발하는 DFA 최소화 문제의 예는 Hopcroft의 알고리즘과 동일하다.알고리즘이 수행하는 단계 수는 n보다 훨씬 작을 수 있으므로(상수 s의 경우) 평균 성능은 알고리즘의 평균 사례 동작을 모델링하기 위해 선택한 자동타에 대한 랜덤 분포에 따라 O(n log n) 또는 심지어 O(n log n)이다.^[6][9]

브조조스키 알고리즘

비결정적 유한자동화(NFA) $M{\displaystyle }$ ${\displaystyle M}$의 전환을 역전시키고$$ 초기 및 최종 상태를^{[note 1]} 전환하면 원래 언어의 역전을 위한$$ $NFA{\displaystyle {}^{}}$ ${\displaystyle M^{}}$ R ${\$ M$^{R}$이 발생한다.표준 파워셋 구조(변환된 DFA의 도달 가능한 상태만 유지)를 사용하여 이 NFA를 DFA로 변환하면 동일한 역방향 언어에$$ 대해 $DFA{\displaystyle {}_{}^{}}$ M ${\displaystyle {}_{}^{}}$ R ${\$가 된다.Brzozowski(1963)가 관찰한 바와 같이, 다시 도달 가능한 상태만을 유지하면서 이 반전과 결정을 두 번 반복하면 원어에 대한 최소한의 DFA가 생성된다.

알고리즘의 이면에 있는 직관은 다음과 같다: 원래 오토메이션에서는 구별되지 않지만, 병합해서는 안 되는 상태(즉, 최소 DFA에서는 병합되지 않음)도 병합할 수 있는 역자동 병합 상태를 결정한다.그런 경우, 두 번째로 자동화를 뒤집은 후에는 결정론적이지 않을 수 있다.그것이 우리가 최소한의 DFA를 획득하면서 그것을 다시 결정해야 하는 이유다.

정확성 증명

After we determinize ${\displaystyle M^{R}}$ to obtain ${\displaystyle M_{D}^{R}}$, we reverse this ${\displaystyle M_{D}^{R}}$ to obtain ${\displaystyle (M_{D}^{R})^{R}=M'}$. Now ${\displaystyle M'}$ has the same language as ${\displaystyle M}$$$그러나 한가지 중요한 차이점이 있다: $M{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$에는 우리가 같은 단어를 받아들일 수 있는 두 개의 상태가 없다는 것이다.$이$는 M D R ${\$ 결정론적인 것에서$$ 따르며, viz. MD$$R {\$displaystyle M_{D}^{R$에 두 개의 상태가 없으며, 이 상태는 초기 ${\displaystyle {}_{}^{}}$에서 동일한 단어를 통해 도달할 수 있다.The determinization of ${\displaystyle M'}$ then creates powerstates (sets of states of ${\displaystyle M'}$), where every two powerstates ${\displaystyle {\mathcal {R}},{\mathcal {S}}}$ differ ‒ naturally ‒ in at least one state ${\displaystyle q}$ of ${\displaystyle M'}$. Assume $$Q∈ R{\displaystyle q\in{{R\mathcal}}}과q∉ P{\displaystyleq\not \in{{P\mathcal}}}, q{\displaystyle q}R{\displaystyle{{R\mathcal}의 언어에}적어도 하나의 word[주 2]기여하}thi부터 시사한 P{\displaystyle{{P\mathcal}에}}선물이 될 수 없[주 3],.s단어uniqu은e ~ $q{\displaystyle }$ ${\displaystyle q}($다른 어떤 상태도 이를 허용하지 않음).우리는 이것이 각 쌍의 파워스테이트에 대해 유지되고, 따라서 각 파워스테이트는 다른 모든 파워스테이트와 구별될 수 있다는 것을 안다.$따라서{\displaystyle }$ $′{\$ M$'}$의 결정 후$,$ 구별할 수 없거나 연결할 수 없는 상태가 없는 DFA가 있으므로 원본 M ${\displaystyle M}$에 대한$$ 최소 DFA ${\$$\}\}\}.$

$M{\displaystyle }$ ${\displaystyle M}$이(가) 이미 결정론적이라면$$ 자르고,^{[note 4]} 뒤집고, 결정하여 다시 되돌리는 것으로 충분하다.이는 입력 FA가 이미 결정론적이기 때문에(그러나 실제로는 반전이 아니라는 것을 명심하라) 위의 프로세스에서$$ $M{\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ R ${\$ M_{$D}^{R}$로 시작하는 것으로 생각할 수 있다.M ${\displaystyle D_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$을(를) 역전하여 결정하는데$,$ $M{\displaystyle }$ ${\$$displaystyle$ $M}$의 언어 역전을 위한 최소 DFA인 ${\$$displaystyle$ ${\overline{M}}$을 얻는다($$지금까지 한 번만 반전을 했으므로).$이제{\displaystyle \stackrel{}{}}$ M$'{\$을(를) 뒤집어서$$ 원어에 대한 최소한의 DFA를 얻는 일만 남았다.

복잡성

Brzozowski 알고리즘의 최악의 경우 복잡성은 입력 자동화의 상태 수에서 기하급수적이다.이것은 입력이 NFA인지 DFA인지에 관계없이 유지된다.DFA의 경우 입력 자동화의 역전을 결정하는 동안 지수 폭발이 발생할 수 있으며,^{[note 5]} NFA의 경우 입력 자동화의 초기 결정 과정에서도 발생할 수 있다.^{[note 6]}그러나 알고리즘은 종종 최악의 경우가 시사하는 것보다 더 좋은 성능을 발휘한다.^[6]

NFA 최소화

위의 절차는 DFA에 대해 효과가 있지만, 분할 방법은 비결정적 유한 자동자(NFA)에 대해서는 효과가 없다.^[10]철저한 검색이 NFA를 최소화할 수 있지만, 일반적으로 거짓으로 여겨지는 계산 복잡성 이론의 미해결 추측인 P=PSPACE가 아닌 한 일반 NFA를 최소화하는 다항 시간 알고리즘은 없다.그러나, NFA 최소화를 위한 방법들은 무차별적인 힘 검색보다 더 효율적일 수 있다.^[11]

참고 항목

• 저전력에 대한 상태 인코딩

메모들

참조

• Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), "4.13 Partitioning", The Design and Analysis of Computer Algorithms, Addison-Wesley, pp. 157–162.
• Berstel, Jean; Boasson, Luc; Carton, Olivier; Fagnot, Isabelle (2010), "Minimization of Automata", Automata: from Mathematics to Applications, European Mathematical Society, arXiv:1010.5318, Bibcode:2010arXiv1010.5318B
• Brzozowski, J. A. (1963), "Canonical regular expressions and minimal state graphs for definite events", Proc. Sympos. Math. Theory of Automata (New York, 1962), Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y., pp. 529–561, MR 0175719.
• Câmpeanu, Cezar; Culik, Karel, II; Salomaa, Kai; Yu, Sheng (2001), "State Complexity of Basic Operations on Finite Languages", 4th International Workshop on Automata Implementation (WIA '99), Lecture Notes in Computer Science, vol. 2214, Springer-Verlag, pp. 60–70, doi:10.1007/3-540-45526-4_6, ISBN 978-3-540-42812-1.
• David, Julien (2012), "Average complexity of Moore's and Hopcroft's algorithms", Theoretical Computer Science, 417: 50–65, doi:10.1016/j.tcs.2011.10.011.
• 기계적(Proc의 Hopcroft, 존(1971년),"최소화하기를 미국 유한 오토머턴에 있는 n로그 n알고리즘", 이론.Internat.Sympos.,Technion, 하이파, 1971년), 뉴욕:학술 출판부를 대신하여 서명함. 189–196, MR0403320.또한 예비 버전, 기술 보고서 STAN-CS-71-190, 스탠퍼드 대학 컴퓨터 과학과, 1월 1971을 참조하십시오.
• Hopcroft, John E.; Ullman, Jeffrey D. (1979), Introduction to Automata Theory, Languages, and Computation, Reading/MA: Addison-Wesley, ISBN 978-0-201-02988-8
• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001), Introduction to Automata Theory, Languages, and Computation (2nd ed.), Addison-Wesley.
• Kameda, Tsunehiko; Weiner, Peter (1970), "On the state minimization of nondeterministic finite automata", IEEE Transactions on Computers, 100 (7): 617–627, doi:10.1109/T-C.1970.222994, S2CID 31188224.
• Knuutila, Timo (2001), "Re-describing an algorithm by Hopcroft", Theoretical Computer Science, 250 (1–2): 333–363, doi:10.1016/S0304-3975(99)00150-4, MR 1795249.
• Leiss, Ernst (1981), "Succinct representation of regular languages by Boolean automata", Theoretical Computer Science, 13 (3): 323–330, doi:10.1016/S0304-3975(81)80005-9, MR 0603263.
• Leiss, Ernst (1985), "Succinct representation of regular languages by Boolean automata II", Theoretical Computer Science, 38: 133–136, doi:10.1016/0304-3975(85)90215-4
• Moore, Edward F. (1956), "Gedanken-experiments on sequential machines", Automata studies, Annals of mathematics studies, no. 34, Princeton, N. J.: Princeton University Press, pp. 129–153, MR 0078059.
• Sakarovitch, Jacques (2009), Elements of automata theory, Translated from French by Reuben Thomas, Cambridge University Press, ISBN 978-0-521-84425-3, Zbl 1188.68177

외부 링크

• Myhill-Nerode 정리를 이용한 DFA 최소화