NFA to DFA 변환: 0(0|1)*1

변환 계약

• 알파벳은 {0, 1}이며 시작 상태, 수용 상태와 모든 NFA 전이를 아래 표와 그림으로 고정합니다.
• DFA의 한 상태는 NFA 상태의 집합입니다. ε-전이가 있으면 각 이동 전후에 ε-closure를 계산합니다.
• 아직 나타나지 않은 전이 결과도 공집합 상태를 포함해 기록해야 완전한 DFA가 됩니다.
• 완료 기준은 시작 부분집합에서 도달 가능한 모든 부분집합을 처리하고, 원본 NFA와 결과 DFA가 같은 수용·거부 표본을 통과하는 것입니다.

1. 정규표현식 및 언어 설명

항목	내용
알파벳(Σ)	{0, 1}
정규표현식	0(0|1)*1
L(0(0|1)*1)	{w ∈ {0,1}* | w는 0으로 시작하고 1로 끝나며 길이 ≥ 2}

---

2. NFA 상태도

flowchart LR
    subgraph "NFA for 0(0|1)*1"
        direction LR
        I([Start]) --> A
        A -- "0" --> B
        B -- "0,1" --> B
        B -- "1" --> C((C))
    end

NFA 설명

• **A**에서 0을 받으면 **B**로 갑니다. (0으로 시작)
• **B**에서는 0이나 1을 받으면 계속 **B**에 머무릅니다. ((0|1)* 부분)
• B**에서 1을 받으면 **C(최종 상태)로 갈 수도 있습니다. (1로 끝남)
• 즉, B**에서 1을 받으면 **B**와 **C 두 곳으로 갈 수 있으므로 NFA입니다.

---

3. Subset Construction (NFA → DFA)

단계별 DFA 상태 도출

1) S₀ =

입력	다음 상태
0	{B} (S₁)
1	오류(∅, Trap)

2) S₁ =

입력	다음 상태
0	{B} (자기 자신)
1	{B, C} (S₂)

3) S₂ = {B, C} (수락 상태)

입력	다음 상태
0	{B} (S₁)
1	{B, C} (자기 자신)

---

4. DFA 상태 변환 표

DFA 상태	NFA 집합	수락 상태?	0 입력 →	1 입력 →
A	{A}	❌	B	Trap(∅)
B	{B}	❌	B	BC
BC	{B, C}	✅	B	BC

---

5. DFA 상태도

flowchart LR
    subgraph "Final DFA"
        direction LR
        I([Start]) --> A
        A -- "0" --> B
        B -- "0" --> B
        B -- "1" --> BC((BC))
        BC -- "0" --> B
        BC -- "1" --> BC
    end

---

6. 예제 문자열 판단

입력 문자열	DFA 진행 경로	Accept?
0110	A → Trap(∅)	❌
1101	A → Trap(∅)	❌
01011010101	A→B→B→BC→B→B→BC→B→B→BC	✅

---