이 섹션에서는 NFA를 동등한 DFA로 변환하는 방법에 대해 설명합니다. NFA에서는 현재 상태에 특정 입력이 제공되면 기계가 여러 상태로 전환됩니다. 주어진 입력 기호에 대해 0개, 1개 또는 2개 이상의 움직임이 있을 수 있습니다. 반면, DFA에서는 현재 상태에 특정 입력이 주어지면 기계는 한 가지 상태로만 이동합니다. DFA는 주어진 입력 기호에 대해 한 번만 이동합니다.

M = (Q, ∑, δ, q0, F)는 언어 L(M)을 허용하는 NFA입니다. L(M) = L(M')이 되도록 M' = (Q', ∑', q0', δ', F')로 표시되는 동등한 DFA가 있어야 합니다.

NFA를 DFA로 변환하는 단계:

1 단계: 초기에 Q' = ψ

2 단계: Q'에 NFA의 q0을 추가합니다. 그런 다음 이 시작 상태에서 전환을 찾습니다.

스캐너 다음

3단계: Q'에서 각 입력 기호에 대해 가능한 상태 집합을 찾습니다. 이 상태 세트가 Q'에 없으면 이를 Q'에 추가합니다.

4단계: DFA에서 최종 상태는 F(NFA의 최종 상태)를 포함하는 모든 상태가 됩니다.

예시 1:

지정된 NFA를 DFA로 변환합니다.

해결책: 주어진 전이 다이어그램에 대해 먼저 전이 테이블을 구성합니다.

이제 우리는 상태 q0에 대한 δ' 전이를 얻을 것입니다.

 δ'([q0], 0) = [q0] δ'([q0], 1) = [q1] 

상태 q1에 대한 δ' 전이는 다음과 같이 얻어집니다.

 δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1] 

상태 q2에 대한 δ' 전이는 다음과 같이 얻어집니다.

 δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2] 

이제 [q1, q2]에서 δ' 전이를 얻을 것입니다.

 δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0) = {q1, q2} ∪ {q2} = [q1, q2] δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2, 1) = {q1} ∪ {q1, q2} = {q1, q2} = [q1, q2] 

상태 [q1, q2]는 최종 상태 q2를 포함하므로 최종 상태이기도 합니다. 구성된 DFA의 전환 테이블은 다음과 같습니다.

전환 다이어그램은 다음과 같습니다.

q2는 도달할 수 없는 상태이기 때문에 상태 q2는 제거될 수 있습니다.

int를 문자열로 변환하는 방법

예시 2:

지정된 NFA를 DFA로 변환합니다.

해결책: 주어진 전이 다이어그램에 대해 먼저 전이 테이블을 구성합니다.

이제 우리는 상태 q0에 대한 δ' 전이를 얻을 것입니다.

 δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] 

상태 q1에 대한 δ' 전이는 다음과 같이 얻어집니다.

 δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1] 

이제 우리는 [q0, q1]에서 δ' 전이를 얻을 것입니다.

 δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] 

비슷하게,

 δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] 

주어진 NFA에서와 같이 q1은 최종 상태이고 DFA에서는 q1이 존재하는 모든 위치가 최종 상태가 됩니다. 따라서 DFA에서 최종 상태는 [q1] 및 [q0, q1]입니다. 따라서 최종 상태 집합 F = {[q1], [q0, q1]}.

구성된 DFA의 전환 테이블은 다음과 같습니다.

자바 업그레이드 어떻게 해?

전환 다이어그램은 다음과 같습니다.

DFA 상태의 이름도 변경할 수 있습니다.

가정하다

 A = [q0] B = [q1] C = [q0, q1] 

이러한 새로운 이름으로 DFA는 다음과 같습니다.