NDFA에서 DFA로 변환

문제 설명

허락하다 X = (Qx, ∑, δx, q0, Fx)L (X) 언어를 허용하는 NDFA 여야합니다. 동등한 DFA를 설계해야합니다.Y = (Qy, ∑, δy, q0, Fy) 그런 L(Y) = L(X). 다음 절차는 NDFA를 동등한 DFA로 변환합니다.

연산

Input − NDFA

Output − 동등한 DFA

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

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

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

Step 4− 가능한 각 입력 알파벳에 대한 상태 {Q 0 , Q 1 , ..., 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의 상태 다이어그램은 다음과 같습니다.