NDFA에서 DFA로 변환

문제 설명

허락하다 X = (Q_x, ∑, δ_x, q₀, F_x)L (X) 언어를 허용하는 NDFA 여야합니다. 동등한 DFA를 설계해야합니다.Y = (Q_y, ∑, δ_y, q₀, F_y) 그런 L(Y) = L(X). 다음 절차는 NDFA를 동등한 DFA로 변환합니다.

연산

Input − NDFA

Output − 동등한 DFA

Step 1 − 주어진 NDFA에서 상태 테이블을 생성합니다.

Step 2 − 동등한 DFA에 대해 가능한 입력 알파벳 아래에 빈 상태 테이블을 만듭니다.

Step 3 − DFA의 시작 상태를 q0 (NDFA와 동일)으로 표시합니다.

Step 4− 가능한 각 입력 알파벳에 대한 상태 {Q ₀ , Q ₁ , ..., Q _n } 조합을 찾습니다 .

Step 5 − 입력 알파벳 열 아래에 새 DFA 상태를 생성 할 때마다 4 단계를 다시 적용해야합니다. 그렇지 않으면 6 단계로 이동합니다.

Step 6 − NDFA의 최종 상태를 포함하는 상태는 동등한 DFA의 최종 상태입니다.

예

아래 그림에 표시된 NDFA를 고려해 보겠습니다.

큐	δ (q, 0)	δ (q, 1)
ㅏ	{에이 비 씨 디이}	{d, e}
비	{씨}	{이자형}
씨	∅	{비}
디	{이자형}	∅
이자형	∅	∅

위의 알고리즘을 사용하여 동등한 DFA를 찾습니다. DFA의 상태 표는 아래와 같습니다.

큐	δ (q, 0)	δ (q, 1)
[ㅏ]	[에이 비 씨 디이]	[d, e]
[에이 비 씨 디이]	[에이 비 씨 디이]	[b, d, e]
[d, e]	[이자형]	∅
[b, d, e]	[c, e]	[이자형]
[이자형]	∅	∅
[c, e]	∅	[비]
[비]	[씨]	[이자형]
[씨]	∅	[비]

DFA의 상태 다이어그램은 다음과 같습니다.