NFA는 주어진 입력 기호에 대해 주어진 상태에서 0개, 1개 또는 1개 이상의 이동을 가질 수 있습니다. NFA에는 NULL 이동(입력 기호 없이 이동)이 있을 수도 있습니다. 반면에 DFA는 주어진 입력 기호에 대해 주어진 상태에서 단 한 번의 이동만 가집니다.
NFA를 DFA로 변환하는 단계:
1단계: 지정된 NFA를 동등한 전이 테이블로 변환
NFA를 동등한 전이 테이블로 변환하려면 모든 상태, 입력 기호 및 전이 규칙을 나열해야 합니다. 전이 규칙은 행렬 형태로 표현되는데, 행은 현재 상태를 나타내고 열은 입력 기호를 나타내며 셀은 다음 상태를 나타냅니다.
2단계: DFA의 시작 상태 만들기
DFA의 시작 상태는 NFA에서 가능한 모든 시작 상태의 집합입니다. 이 세트를 NFA 시작 상태의 엡실론 폐쇄라고 합니다. 엡실론 폐쇄는 엡실론(?) 전환을 따라 시작 상태에서 도달할 수 있는 모든 상태의 집합입니다.
스캐너 다음
3단계: DFA의 전환 테이블 만들기
DFA의 전환 테이블은 NFA의 전환 테이블과 유사하지만 개별 상태 대신 행과 열이 상태 집합을 나타냅니다. 각 입력 기호에 대해 전이 테이블의 해당 셀에는 NFA 전이 테이블의 전이 규칙을 따라 얻은 상태 집합의 엡실론 폐쇄가 포함됩니다.
4단계: DFA의 최종 상태 만들기
DFA의 최종 상태는 NFA의 최종 상태를 하나 이상 포함하는 상태 집합입니다.
5단계: DFA 단순화
이전 단계에서 얻은 DFA에는 불필요한 상태와 전환이 포함될 수 있습니다. DFA를 단순화하기 위해 다음 기술을 사용할 수 있습니다.
- 도달할 수 없는 상태 제거: 시작 상태에서 도달할 수 없는 상태는 DFA에서 제거될 수 있습니다.
- 데드 상태 제거: 최종 상태로 이어질 수 없는 상태는 DFA에서 제거될 수 있습니다.
- 등가 상태 병합: 모든 입력 기호에 대해 동일한 전환 규칙을 갖는 상태를 단일 상태로 병합할 수 있습니다.
6단계: 더 이상 단순화할 수 없을 때까지 3~5단계를 반복합니다.
DFA를 단순화한 후 더 이상 단순화할 수 없을 때까지 3~5단계를 반복합니다. 획득된 최종 DFA는 주어진 NFA와 동등한 최소화된 DFA입니다.
int를 문자열로 변환하는 방법
예: 그림 1에 표시된 다음 NFA를 고려하십시오.
다음은 NFA의 다양한 매개변수입니다. Q = {q0, q1, q2 } ? = (a, b) F = { q2 } ? (NFA의 전환 기능)
1단계: Q' = ? 2단계: Q' = {q0} 3단계: Q'의 각 상태에 대해 각 입력 기호의 상태를 찾습니다. 현재 Q'의 상태는 q0이고, NFA의 전이 함수를 사용하여 입력 기호 a와 b의 q0에서 이동을 찾고 DFA의 전이 테이블을 업데이트합니다. ?'(DFA의 전환 기능)
이제 { q0, q1 }은 단일 상태로 간주됩니다. 해당 항목이 Q'에 없으므로 Q'에 추가합니다. 따라서 Q' = { q0, { q0, q1 } } 이제 다른 입력 기호의 상태 { q0, q1 }에서 이동이 DFA의 전환 테이블에 존재하지 않습니다. 다음과 같이 계산합니다. , 가) = ? ( q0, a ) ? ? ( q1, a ) = { q0, q1 } ?' ( { q0, q1 }, b ) = ? (q0,b) ? ? ( q1, b ) = { q0, q2 } 이제 DFA의 전환 테이블을 업데이트하겠습니다. ?'(DFA의 전환 기능)
자바 업그레이드 어떻게 해?
이제 { q0, q2 }는 단일 상태로 간주됩니다. 해당 항목이 Q'에 없으므로 Q'에 추가합니다. 따라서 Q' = { q0, { q0, q1 }, { q0, q2 } } 이제 다른 입력 기호의 상태 {q0, q2}에서 이동은 DFA의 전환 테이블에 존재하지 않습니다. 다음과 같이 계산합니다. ( { q0, q2 }, a ) = ? ( q0, a ) ? ? ( q2, a ) = { q0, q1 } ?' ( { q0, q2 }, b ) = ? (q0,b) ? ? ( q2, b ) = { q0 } 이제 DFA의 전환 테이블을 업데이트하겠습니다. ?'(DFA의 전환 기능)
새로운 상태가 생성되지 않았으므로 변환이 완료되었습니다. DFA의 최종 상태는 q2를 구성요소로 갖는 상태입니다. 즉, { q0, q2 } 다음은 DFA의 다양한 매개변수입니다. Q' = { q0, { q0, q1 }, { q0, q2 } } ? = ( a, b ) F = { { q0, q2 } } 및 전이 함수 ?'는 위와 같습니다. 위의 NFA에 대한 최종 DFA는 그림 2에 나와 있습니다.
메모 : 때로는 정규 표현식을 DFA로 변환하는 것이 쉽지 않습니다. 먼저 정규식을 NFA로 변환한 다음 NFA를 DFA로 변환할 수 있습니다.
질문 : 정규식 (0 + 1)* (10)에 해당하는 최소 결정론적 유한 자동 장치의 상태 수는 ____________입니다.
해결책 : 먼저 위의 표현식에 대해 NFA를 만들어 보겠습니다. (0 + 1)*에 대한 NFA를 만들기 위해 NFA는 입력 기호 0 또는 1에서 동일한 상태 q0에 있습니다. 그런 다음 연결을 위해 표시된 대로 두 개의 이동(1의 경우 q0에서 q1, 0의 경우 q1에서 q2)을 추가합니다. 그림 3에서.
이 기사는 Sonal Tuteja가 기고했습니다.