NFA to DFA Conversion: Subset Construction

이제 주어진 NFA(비결정론적 유한 오토마타)를 DFA(결정론적 유한 오토마타)로 변환하는 방법을 살펴보겠습니다.

때때로 DFA를 직접 구성하는 것보다 NFA를 먼저 만들고 나서 이를 DFA로 변환하는 것이 더 나은 접근 방식이 될 수 있습니다. 그래서 우리는 먼저 NFA를 만들고, 이후에 DFA로 변환하는 과정을 진행할 것입니다.

이제 변환 과정이 얼마나 간단한지 살펴보겠습니다.
주어진 NFA는 상태 집합, 입력 알파벳(예: ε 포함 가능), 전이 함수, 그리고 NFA의 최종 상태(accepting states) 등으로 정의됩니다.
이러한 NFA를 등가적인 DFA로 변환하는 것이 우리의 목표입니다.

그렇다면 변환 방법을 알아보겠습니다.

NFA를 DFA로 변환하는 과정은 몇 가지 단계로 이루어지며, 이를 이해하기 위해 간단한 예제를 통해 살펴보겠습니다.

1. 초기 상태 설정
   • 우선, DFA의 초기 상태를 설정합니다.
   • NFA의 초기 상태(예: q₀)가 DFA에서도 초기 상태가 됩니다.
   • 또한, ε-전이를 고려하여 NFA의 초기 상태에서 도달할 수 있는 모든 상태를 포함해야 합니다.
2. 상태 집합을 확장
   • 초기 상태에서 가능한 모든 전이를 확인하여 새로운 상태 집합을 생성합니다.
   • 각 입력 심볼(예: a, b 등)에 대해 현재 상태에서 이동할 수 있는 모든 상태를 확인하고, 이를 새로운 상태로 추가합니다.
   • 만약 새로운 상태 집합이 DFA에 존재하지 않는다면, 새로운 상태로 추가합니다.
3. 새로운 상태들의 전이 정의
   • DFA에서는 하나의 상태에서 특정 입력 심볼을 받으면 반드시 하나의 상태로 이동해야 합니다.
   • 하지만 NFA에서는 여러 상태로 이동할 수 있으므로, 이러한 상태들을 하나의 집합으로 묶어 새로운 상태로 정의합니다.
   • 예를 들어, 어떤 상태에서 입력 심볼 ‘a’를 받았을 때 {q₁, q₂, q₃}와 같은 상태 집합으로 이동할 수 있다면, 이 상태 집합을 하나의 새로운 상태로 간주합니다.
4. 최종 상태 결정
   • NFA에서 하나라도 최종 상태(accepting state)에 속하는 상태가 있다면, 해당 상태 집합은 DFA에서도 최종 상태가 됩니다.

이러한 과정을 거치면, NFA를 등가적인 DFA로 변환할 수 있습니다.
이제 다음 강의에서 구체적인 예제를 통해 이 과정을 더 자세히 살펴보겠습니다.

---

이제 주어진 NFA(비결정론적 유한 오토마타)를 DFA(결정론적 유한 오토마타)로 변환하는 방법을 살펴보겠습니다.

지난 강의에서 변환 알고리즘을 다루었으니, 이번에는 실제 예제를 통해 변환 과정을 자세히 이해해 보겠습니다.

먼저, 항상 초기 상태에서 시작합니다.
여기서 초기 상태는 q₀라고 하겠습니다.

1. 초기 상태의 전이 관계 확인

우리는 q₀에서 입력 심볼 0을 받았을 때 어디로 이동하는지를 확인해야 합니다.

• q₀에서 0을 입력받으면 q₀과 q₁으로 이동합니다.
  • 즉, 새로운 상태 집합 {q₀, q₁}이 생성됩니다.
• q₀에서 1을 입력받으면 자기 자신(q₀)으로 이동합니다.

이제 우리는 새로운 상태 {q₀, q₁}을 고려해야 합니다.
이 상태에서 입력 심볼 0과 1을 받을 때 어디로 이동하는지 살펴봅니다.

2. 새로운 상태들의 전이 관계 확인

• {q₀, q₁}에서 입력 0을 받으면
  • q₀에서 0을 받으면 {q₀, q₁}
  • q₁에서 0을 받으면 그대로 q₁
  • 따라서 {q₀, q₁}에서 0을 받으면 {q₀, q₁}로 이동
• {q₀, q₁}에서 입력 1을 받으면
  • q₀에서 1을 받으면 q₀
  • q₁에서 1을 받으면 q₂
  • 따라서 {q₀, q₁}에서 1을 받으면 {q₀, q₁, q₂}로 이동
  • 새로운 상태 {q₀, q₁, q₂}이 생성됨

이제 새로운 상태 {q₀, q₁, q₂}에 대해 전이 관계를 확인합니다.

3. 새로운 상태 {q₀, q₁, q₂}의 전이 관계 확인

• {q₀, q₁, q₂}에서 입력 0을 받으면
  • q₀에서 0을 받으면 {q₀, q₁}
  • q₁에서 0을 받으면 q₁
  • q₂는 0에 대한 전이가 없음
  • 따라서 {q₀, q₁, q₂}에서 0을 받으면 {q₀, q₁}로 이동
• {q₀, q₁, q₂}에서 입력 1을 받으면
  • q₀에서 1을 받으면 q₀
  • q₁에서 1을 받으면 q₂
  • q₂에서 1을 받으면 q₂
  • 따라서 {q₀, q₁, q₂}에서 1을 받으면 {q₀, q₁, q₂}로 이동

4. DFA의 최종 상태 결정

NFA에서 최종 상태(accepting state)는 q₂였습니다.
그러므로, q₂를 포함하는 모든 상태 집합이 DFA에서도 최종 상태가 됩니다.
즉, {q₀, q₁, q₂}가 최종 상태가 됩니다.

5. 최종 DFA 구성

이제 우리가 찾은 상태들과 전이 관계를 정리하면 다음과 같은 DFA가 생성됩니다.

현재 상태	입력 0 → 다음 상태	입력 1 → 다음 상태
{q₀}	{q₀, q₁}	{q₀}
{q₀, q₁}	{q₀, q₁}	{q₀, q₁, q₂}
{q₀, q₁, q₂}	{q₀, q₁}	{q₀, q₁, q₂}

최종 상태는 {q₀, q₁, q₂}입니다.

이제 이 상태 전이 테이블을 바탕으로 상태들을 노드로 하고, 입력 심볼에 따라 이동하는 DFA 상태 다이어그램을 그릴 수 있습니다.

---

이렇게 하면 주어진 NFA를 DFA로 변환하는 과정이 정리됩니다.
이 방법은 특히 경쟁 시험(competitive exams)을 준비할 때 유용하며, 직접 상태 다이어그램을 그리기 전에 표를 작성하면 더 빠르게 변환할 수 있습니다.

이제 첫 번째 예제를 마쳤습니다. 다음 강의에서는 더 복잡한 예제를 다뤄보겠습니다.

---

이제 주어진 NFA(비결정론적 유한 오토마타)를 DFA(결정론적 유한 오토마타)로 변환하는 연습을 더 해보겠습니다.

이전 강의에서 알고리즘과 예제 하나를 다루었으므로, 이를 바탕으로 추가적인 연습을 진행해 보겠습니다.

이번 경우에도 NFA는 세 개의 상태(Q₀, Q₁, Q₂)를 가지고 있으며, 이를 DFA로 변환하는 과정에서 전이 테이블을 구성하는 방법을 사용하겠습니다.

---

1. DFA의 상태 전이 테이블 초기화

먼저 DFA의 상태 전이 테이블을 만들기 위해 다음과 같은 세 개의 열(columns)을 설정합니다.
각 열은 입력 심볼에 대한 상태 변화를 나타냅니다.

현재 상태	입력 0 → 다음 상태	입력 1 → 다음 상태
Q₀	?	?
Q₁	?	?
Q₂	?	?

NFA의 초기 상태인 Q₀부터 시작하겠습니다.

---

2. 초기 상태(Q₀)의 전이 관계 분석

• Q₀에서 입력 0을 받으면
  • 자기 자신(Q₀)으로 이동
• Q₀에서 입력 1을 받으면
  • Q₁으로 이동

이제 Q₀의 전이 관계를 테이블에 채워 넣습니다.

현재 상태	입력 0 → 다음 상태	입력 1 → 다음 상태
Q₀	{Q₀}	{Q₁}

---

3. 새로운 상태(Q₁)의 전이 관계 분석

• Q₁에서 입력 0을 받으면
  • 자기 자신(Q₁)과 Q₂로 이동 → {Q₁, Q₂}
• Q₁에서 입력 1을 받으면
  • 자기 자신(Q₁)으로 이동

이를 테이블에 추가하면 다음과 같습니다.

현재 상태	입력 0 → 다음 상태	입력 1 → 다음 상태
Q₀	{Q₀}	{Q₁}
Q₁	{Q₁, Q₂}	{Q₁}

새로운 상태 {Q₁, Q₂}가 생성되었으므로, 이 상태에 대한 전이 관계를 추가적으로 확인해야 합니다.

---

4. 새로운 상태({Q₁, Q₂})의 전이 관계 분석

• {Q₁, Q₂}에서 입력 0을 받으면
  • Q₁에서 0을 받으면 {Q₁, Q₂}
  • Q₂에서 0을 받으면 자기 자신(Q₂) → {Q₁, Q₂}
• {Q₁, Q₂}에서 입력 1을 받으면
  • Q₁에서 1을 받으면 Q₁
  • Q₂에서 1을 받으면 Q₂
  • 따라서 {Q₁, Q₂}에서 1을 받으면 그대로 {Q₁, Q₂}

이제 테이블을 업데이트하면 다음과 같습니다.

현재 상태	입력 0 → 다음 상태	입력 1 → 다음 상태
Q₀	{Q₀}	{Q₁}
Q₁	{Q₁, Q₂}	{Q₁}
{Q₁, Q₂}	{Q₁, Q₂}	{Q₁, Q₂}

---

5. DFA의 최종 상태 결정

NFA에서 최종 상태(accepting state)는 Q₂였습니다.
DFA에서 최종 상태를 결정할 때는, Q₂를 포함하는 모든 상태 집합이 최종 상태가 됩니다.

따라서 {Q₁, Q₂}가 DFA에서 최종 상태가 됩니다.

---

1. 초기 상태 설정

주어진 NFA에서 초기 상태는 Q₀입니다.

• Q₀에서 입력 0을 받으면
  • 자기 자신(Q₀)과 Q₁으로 이동 → {Q₀, Q₁}
• Q₀에서 입력 1을 받으면
  • Q₁로 이동

새로운 상태 {Q₀, Q₁}이 생성되었으므로, 이를 고려해야 합니다.

현재 상태	입력 0 → 다음 상태	입력 1 → 다음 상태
Q₀	{Q₀, Q₁}	{Q₁}

---

2. 새로운 상태 {Q₀, Q₁}의 전이 관계 확인

• {Q₀, Q₁}에서 입력 0을 받으면
  • Q₀에서 0을 받으면 {Q₀, Q₁}
  • Q₁에서 0을 받으면 아무 곳에도 이동하지 않음
  • 따라서 {Q₀, Q₁}에서 0을 받으면 {Q₀, Q₁}
• {Q₀, Q₁}에서 입력 1을 받으면
  • Q₀에서 1을 받으면 {Q₁}
  • Q₁에서 1을 받으면 {Q₀, Q₁}
  • 따라서 {Q₀, Q₁}에서 1을 받으면 {Q₀, Q₁}

새로운 상태 {Q₁}이 생성되었으므로, 이를 고려해야 합니다.

현재 상태	입력 0 → 다음 상태	입력 1 → 다음 상태
Q₀	{Q₀, Q₁}	{Q₁}
{Q₀, Q₁}	{Q₀, Q₁}	{Q₀, Q₁}

---

3. 새로운 상태 {Q₁}의 전이 관계 확인

• {Q₁}에서 입력 0을 받으면
  • Q₁에서 0을 받으면 이동할 곳 없음 (즉, dead state)
  • 따라서 {Q₁}에서 0을 받으면 ∅
• {Q₁}에서 입력 1을 받으면
  • Q₁에서 1을 받으면 {Q₀, Q₁}
  • 따라서 {Q₁}에서 1을 받으면 {Q₀, Q₁}

최종적으로 테이블을 업데이트하면 다음과 같습니다.

현재 상태	입력 0 → 다음 상태	입력 1 → 다음 상태
Q₀	{Q₀, Q₁}	{Q₁}
{Q₀, Q₁}	{Q₀, Q₁}	{Q₀, Q₁}
{Q₁}	∅	{Q₀, Q₁}

---

4. DFA의 최종 상태 결정

NFA에서 최종 상태(accepting state)는 Q₁였습니다.
DFA에서 최종 상태를 결정할 때는, Q₁를 포함하는 모든 상태 집합이 최종 상태가 됩니다.

따라서 {Q₁}, {Q₀, Q₁}가 DFA에서 최종 상태가 됩니다.

---

부분 집합 구성법(Subset Construction)에 대한 간단한 논의

이제 DFA(결정론적 유한 오토마타)를 만드는 과정에서 중요한 개념인 부분 집합 구성법(Subset Construction)에 대해 간단히 논의해보겠습니다.

이전 강의에서 NFA(비결정론적 유한 오토마타)를 DFA로 변환하는 방법을 배웠습니다.
이제 이를 바탕으로 변환 과정에서 발생하는 몇 가지 중요한 개념을 추론해볼 것입니다.

---

1. 왜 NFA에서 DFA로 변환할까?

DFA를 직접 구성하는 것이 어려운 경우가 많기 때문에, 먼저 NFA를 설계한 후 이를 DFA로 변환하는 방식이 더 유용할 수 있습니다.
이것이 바로 부분 집합 구성법(Subset Construction)의 기본 개념입니다.

즉, NFA가 주어졌을 때, 이를 DFA로 변환하는 과정이 결정 가능(decidable)한 문제임을 이해하는 것이 중요합니다.
이는 알고리즘을 적용하면 언제나 해결할 수 있는 문제라는 의미입니다.

---

2. NFA의 상태 개수와 DFA의 최대 상태 개수

NFA에서 DFA로 변환할 때, 중요한 질문 중 하나는 "DFA의 상태 개수는 최대 몇 개까지 될 수 있는가?"입니다.

만약 NFA의 상태 개수가 n이라면, DFA에서 가능한 모든 상태의 개수는 최대 2ⁿ개가 될 수 있습니다.
이는 각 상태가 포함될 수도 있고 포함되지 않을 수도 있기 때문에, 가능한 모든 부분 집합을 고려해야 하기 때문입니다.

예제: NFA의 상태가 3개(Q₀, Q₁, Q₂)인 경우

이 경우 DFA에서 생성될 수 있는 최대 상태 개수는 2³ = 8개입니다.
실제 DFA에서는 이보다 적을 수도 있지만, 최악의 경우 8개의 상태가 필요할 수도 있습니다.

아래는 가능한 상태들의 조합 예시입니다.

1. ∅ (공집합, 아무 상태도 포함하지 않는 경우)
2. {Q₀}
3. {Q₁}
4. {Q₂}
5. {Q₀, Q₁}
6. {Q₀, Q₂}
7. {Q₁, Q₂}
8. {Q₀, Q₁, Q₂}

따라서, NFA에 n개의 상태가 있다면, DFA는 최대 2ⁿ개의 상태를 가질 수 있음을 알 수 있습니다.
하지만 실제로는 모든 상태가 사용되지 않을 수도 있으며, 일부 상태는 존재하지 않을 수도 있습니다.

---

3. 부분 집합 구성법(Subset Construction)의 의미

부분 집합 구성법은 NFA의 상태 집합을 활용하여 DFA의 상태를 구성하는 방법입니다.
즉, DFA의 각 상태는 NFA에서 도달할 수 있는 상태들의 집합으로 표현됩니다.

이 방법을 통해 DFA의 상태 개수를 예측하고, 최악의 경우에도 변환이 가능함을 보장할 수 있습니다.
하지만 실제로는 DFA의 상태 개수가 2ⁿ개보다 적게 나오는 경우가 많습니다.

---

4. 결론 및 다음 강의 예고

이번 논의에서는 NFA에서 DFA로 변환할 때 최대 상태 개수와 부분 집합 구성법의 개념을 살펴보았습니다.
다음 강의에서는 구체적인 예제를 통해 부분 집합 구성법이 어떻게 적용되는지 알아보겠습니다.

---

부분 집합 구성법(Subset Construction) 예제

이번에는 부분 집합 구성법(Subset Construction)을 이용하여 주어진 언어에 대한 DFA를 구성하는 과정을 살펴보겠습니다.

주어진 문제는 다음 조건을 만족하는 모든 이진 문자열을 인식하는 DFA를 구성하는 것입니다.

1. 문자열의 길이가 짝수인 경우
2. 문자열이 10으로 시작하는 경우

이제 이 언어를 인식하는 DFA를 직접 설계하는 대신, 먼저 NFA를 구성한 후 이를 DFA로 변환하는 방법을 사용하겠습니다.

---

1. NFA 구성

먼저 주어진 조건을 만족하는 NFA(비결정론적 유한 오토마타)를 설계해 보겠습니다.

(1) 짝수 길이 문자열을 인식하는 NFA

• 문자열의 길이가 짝수인 경우를 인식해야 하므로, 초기 상태(Q₀)를 최종 상태로 설정합니다.
• 입력을 하나 받을 때마다 상태를 전환하여 Q₁ → Q₂ → Q₁ → Q₂ 형태로 진행되도록 만듭니다.
• 즉, 입력을 하나 받을 때마다 홀수 길이(Q₁)와 짝수 길이(Q₂)를 번갈아 가며 이동하게 됩니다.
• 최종 상태는 짝수 길이에서 멈추는 Q₂입니다.

(2) 1로 시작하는 문자열 중 "10"으로 시작하는 경우를 추가

• 1로 시작하는 문자열을 처리하기 위해 Q₃ 상태를 도입하고, 이후 0을 만나면 Q₄(최종 상태)로 이동하도록 설계합니다.
• Q₄ 상태에서는 이후 어떤 입력을 받더라도 최종 상태를 유지해야 합니다.

이제 이를 바탕으로 NFA의 상태를 정리하면 다음과 같습니다.

1. Q₀ → 초기 상태 (짝수 길이이므로 최종 상태)
2. Q₀ → 입력 0,1 → Q₁ (홀수 길이)
3. Q₁ → 입력 0,1 → Q₂ (짝수 길이)
4. Q₂ → 입력 0,1 → Q₁ (홀수 길이)
5. Q₀ → 입력 1 → Q₃ (1로 시작하는 문자열)
6. Q₃ → 입력 0 → Q₄ ("10"으로 시작하는 문자열 → 최종 상태)
7. Q₄ → 입력 0 또는 1 → Q₄ (최종 상태 유지)

이제 이 NFA를 DFA로 변환해 보겠습니다.

---

2. DFA 변환 과정

이제 NFA의 상태 집합을 이용하여 부분 집합 구성법(Subset Construction)을 적용해 DFA를 생성하겠습니다.

(1) 초기 상태 설정 (Q₀)

• Q₀은 NFA에서도 초기 상태이며, 최종 상태입니다.
• 따라서 DFA에서도 초기 상태는 Q₀이고, 최종 상태로 설정됩니다.

(2) Q₀에서 입력에 따른 전이 확인

• 입력 0을 받으면 Q₁으로 이동
• 입력 1을 받으면 Q₃으로 이동

DFA 상태 테이블을 작성하면 다음과 같습니다.

현재 상태	입력 0 → 다음 상태	입력 1 → 다음 상태
Q₀	Q₁	Q₁, Q₃

(3) 새로운 상태 Q₁의 전이 확인

• 입력 0을 받으면 Q₂로 이동 (짝수 길이)
• 입력 1을 받으면 Q₂로 이동 (홀수 길이 + 1)

현재 상태	입력 0 → 다음 상태	입력 1 → 다음 상태
Q₀	Q₁	Q₁, Q₃
Q₁	Q₂	Q₂

(4) 새로운 상태 Q₂의 전이 확인

• 입력 0을 받으면 다시 Q₁으로 이동 (홀수 길이)
• 입력 1을 받으면 다시 Q₁으로 이동

현재 상태	입력 0 → 다음 상태	입력 1 → 다음 상태
Q₀	Q₁	Q₁, Q₃
Q₁	Q₂	Q₂
Q₂	Q₁	Q₁

(5) 새로운 상태 {Q₁, Q₃}의 전이 확인

• {Q₁, Q₃}에서 입력 0을 받으면
  • Q₁에서 입력 0을 받으면 Q₂로 이동
  • Q₃에서 입력 0을 받으면 Q₄로 이동(10을 만족)
• {Q₁, Q₃}에서 입력 1을 받으면
  • Q₁에서 입력 1을 받으면 Q₂로 이동
  • Q₃에서 입력 1을 받으면 어디로도 이동하지 않음

현재 상태	입력 0 → 다음 상태	입력 1 → 다음 상태
Q₀	Q₁	Q₁, Q₃
Q₁	Q₂	Q₂
Q₂	Q₁	Q₁
Q₁, Q₃	Q₂, Q₄	Q₂

(6) 새로운 상태 {Q₂, Q₄}의 전이 확인

• {Q₂, Q₄}에서 입력 0을 받으면
  • Q₂에서 입력 0을 받으면 Q₁로 이동
  • Q₄에서 입력 0을 받으면 Q₄로 이동
• {Q₂, Q₄}에서 입력 1을 받으면
  • Q₂에서 입력 1을 받으면 Q₁로 이동
  • Q₄에서 입력 1을 받으면 Q₄로 이동

현재 상태	입력 0 → 다음 상태	입력 1 → 다음 상태
Q₀	Q₁	Q₁, Q₃
Q₁	Q₂	Q₂
Q₂	Q₁	Q₁
Q₁, Q₃	Q₂, Q₄	Q₂
Q₂, Q₄	Q₁, Q₄	Q₁, Q₄

(6) 새로운 상태 {Q₁, Q₄}의 전이 확인

• {Q₁, Q₄}에서 입력 0을 받으면
  • Q₁에서 입력 0을 받으면 Q₂로 이동
  • Q₄에서 입력 0을 받으면 Q₄로 이동
• {Q₁, Q₄}에서 입력 1을 받으면
  • Q₁에서 입력 1을 받으면 Q₂로 이동
  • Q₄에서 입력 1을 받으면 Q₄로 이동

현재 상태	입력 0 → 다음 상태	입력 1 → 다음 상태
Q₀	Q₁	Q₁, Q₃
Q₁	Q₂	Q₂
Q₂	Q₁	Q₁
Q₁, Q₃	Q₂, Q₄	Q₂
Q₂, Q₄	Q₁, Q₄	Q₁, Q₄
Q₁, Q₄	Q₂, Q₄	Q₂, Q₄

---

3. DFA의 최종 상태 설정

DFA에서 최종 상태는 NFA에서 최종 상태(Q₀, Q₂, Q₄)를 포함하는 모든 상태입니다.

따라서 DFA에서 최종 상태는 {Q₀}, {Q₂}, {Q₂, Q₄}, {Q₁, Q₄}가 됩니다.

여기서 추가적으로 단순화를 진행하여

현재 상태	입력 0 → 다음 상태	입력 1 → 다음 상태
Q₀	Q₁	Q₁, Q₃
Q₁	Q₂	Q₂
Q₂	Q₁	Q₁
Q₁, Q₃	Q₂, Q₄	Q₂
Q₂, Q₄	Q₂, Q₄	Q₂, Q₄

와 같이 만들 수도 있다.

원래 {Q₂, Q₄}에서는 {Q₁, Q₄}로 전이하지만, 최종 상태에 머무르는 건 똑같기 때문에, 0과 1을 입력받았을 때 자기 자신으로 향하는 전이로 단순화할 수 있다.

부분 집합 구성법(Subset Construction) 예제

이번에는 부분 집합 구성법(Subset Construction)을 이용하여 주어진 언어에 대한 DFA(결정론적 유한 오토마타)를 구성하는 과정을 살펴보겠습니다.

1. 주어진 언어의 정의

주어진 언어 L은 "모든 이진 문자열 중 101 또는 011로 끝나는 문자열"입니다.
즉, 수용(accept)해야 하는 문자열은 다음과 같습니다.

• 101, 011
• 1101, 0011, 010101, 100011 등

이제 이 언어를 인식하는 DFA를 직접 설계하는 대신, 먼저 NFA(비결정론적 유한 오토마타, NFA)를 설계한 후 이를 DFA로 변환하는 방법을 사용하겠습니다.

---

2. NFA 구성

주어진 조건을 만족하는 NFA를 설계해 보겠습니다.

(1) 101로 끝나는 문자열을 인식하는 NFA

1. 초기 상태 Q₀에서 1을 입력 받으면 Q₁으로 이동
2. Q₁에서 0을 입력 받으면 Q₂로 이동
3. Q₂에서 1을 입력 받으면 Q₃으로 이동
4. Q₃는 최종 상태(Accepting State)

(2) 011로 끝나는 문자열을 인식하는 NFA

1. 초기 상태 Q₀에서 0을 입력 받으면 Q₄로 이동
2. Q₄에서 1을 입력 받으면 Q₅로 이동
3. Q₅에서 1을 입력 받으면 Q₃으로 이동 (최종 상태)

(3) Q₀에서 Q₀로 전이

• 0이나 1을 받으면 자기 자신으로 돌아가는 이유는, 유효한 패턴(101 또는 011)이 나타나기 전까지 의미 없는 접두어를 무시하며 대기하기 위해서입니다.

---

3. NFA 상태 정리

1. Q₀ → 초기 상태 (어떤 문자열이든 올 수 있음, 패턴을 찾기 전 대기 상태)
2. Q₀ → 입력 0 → {Q₀, Q₄} (패턴을 찾기 전 대기 또는 "011 감지 시작")
3. Q₀ → 입력 1 → {Q₀, Q₁} (패턴을 찾기 전 대기 또는 "101 감지 시작")
4. Q₁ → 입력 0 → Q₂ ("10" 부분 감지)
5. Q₂ → 입력 1 → Q₃ ("101"을 완성, 최종 상태)
6. Q₄ → 입력 1 → Q₅ ("01" 부분 감지)
7. Q₅ → 입력 1 → Q₃ ("011"을 완성, 최종 상태)
8. Q₃ → 최종 상태 ("101" 또는 "011"로 끝나는 문자열 수용)

---

4. DFA로 변환 (Subset Construction 적용)

이제 부분 집합 구성법을 사용하여 DFA를 구성하겠습니다.
DFA의 각 상태는 NFA 상태들의 집합으로 이루어집니다.

(1) 초기 상태 설정 (Q₀)

• DFA의 초기 상태는 {Q₀}
• NFA에서 Q₀은 입력 0을 받으면 Q₄로, 입력 1을 받으면 Q₁으로 이동할 수 있음
• 따라서 DFA의 초기 상태는 다음과 같이 확장됨:
  • 입력 0 → {Q₀, Q₄}
  • 입력 1 → {Q₀, Q₁}

(2) DFA 상태 전이 테이블 구성

DFA 상태	포함된 NFA 상태들	입력 0 → 다음 상태	입력 1 → 다음 상태
{Q₀}	Q₀	{Q₀, Q₄}	{Q₀, Q₁}
{Q₀, Q₄}	Q₀, Q₄	{Q₀, Q₄}	{Q₀, Q₁, Q₅}
{Q₀, Q₁}	Q₀, Q₁	{Q₀, Q₄, Q₂}	{Q₀, Q₁}
{Q₀, Q₁, Q₅}	Q₀, Q₁, Q₅	{Q₀, Q₄, Q₂}	{Q₀, Q₁, Q₃}
{Q₀, Q₄, Q₂}	Q₀, Q₄, Q₂	{Q₀, Q₄}	{Q₀, Q₁, Q₃, Q₅}
{Q₀, Q₁, Q₃}	Q₀, Q₁, Q₃	{Q₀, Q₄, Q₂}	{Q₀, Q₁}
{Q₀, Q₁, Q₅, Q₃}	Q₀, Q₁, Q₅, Q₃	{Q₀, Q₄, Q₂}	{Q₀, Q₁, Q₃}

• 최종 상태: Q₃을 포함하는 모든 상태 → {Q₀, Q₁, Q₃}, {Q₀, Q₁, Q₅, Q₃}