사용 개념: 부분집합 구성법의 ε-closure와 네 단계.
“NFA를 DFA로 바꿔라”는 문제는 같은 하위목표의 되풀이다. ① 시작 묶음: \(T_0 = \epsilon\text{-}closure(\text{시작 상태})\) ② 한 칸 채우기: 묶음 하나와 기호 하나를 골라 \(\delta\)로 옮긴 뒤 ε-closure를 구한다 ③ 이름 붙이기: 처음 보는 묶음이면 새 \(T_i\), 본 것이면 그 이름을 적는다 ④ 멈춤 확인: 모든 묶음의 모든 칸을 채웠으면 멈춘다 ⑤ 받아들이는 상태: NFA의 받아들이는 상태가 하나라도 든 묶음을 고른다1.
문제 1 · 완전한 풀이
\((0 \mid 1)^*00\)의 NFA다. \(q_0\)에서 0과 1로 \(q_0\), \(q_0\)에서 0으로 \(q_1\), \(q_1\)에서 0으로 \(q_2\). 시작 \(q_0\), 받아들이는 상태 \(q_2\).
- 시작 묶음: ε-전이가 없다. \(T_0 = \{q_0\}\).
- 한 칸 채우기 (\(T_0\), 0): \(q_0\)에서 0으로 \(q_0\)과 \(q_1\). \(\{q_0, q_1\}\). 이름 붙이기: 처음 본다. \(T_1\).
- 한 칸 채우기 (\(T_0\), 1): \(\{q_0\}\). 이름 붙이기: \(T_0\).
- 한 칸 채우기 (\(T_1\), 0): \(q_0\)에서 \(q_0, q_1\), \(q_1\)에서 \(q_2\). \(\{q_0, q_1, q_2\}\). 이름 붙이기: 처음 본다. \(T_2\).
- 한 칸 채우기 (\(T_1\), 1): \(q_0\)에서 \(q_0\). \(q_1\)은 1로 갈 곳이 없다. \(\{q_0\} = T_0\).
- 한 칸 채우기 (\(T_2\), 0): \(\{q_0, q_1, q_2\} = T_2\). (\(T_2\), 1): \(\{q_0\} = T_0\).
- 멈춤 확인: 세 묶음의 여섯 칸을 다 채웠고 새 묶음이 없다.
- 받아들이는 상태: \(q_2\)가 든 것은 \(T_2\)뿐이다.
| 0 | 1 | |
|---|---|---|
| \(T_0\) | \(T_1\) | \(T_0\) |
| \(T_1\) | \(T_2\) | \(T_0\) |
| \(T_2\) | \(T_2\) | \(T_0\) |
\(T_0, T_1, T_2\)를 \(q_0, q_1, q_2\)로 바꿔 읽으면 \((0 \mid 1)^*00\)을 받아들이는 세 상태짜리 DFA가 된다. \(q_0\)은 “끝에 0이 없다”, \(q_1\)은 “끝이 0 하나다”, \(q_2\)는 “끝이 00이다”를 뜻한다2.
문제 2 · 마지막 하위목표만 빈칸
\(a^*b\)를 톰슨 구성법으로 만든 NFA다. 상태 1~6, 시작 1, 받아들이는 상태 6.
- ε-화살표: 1→2, 1→4, 3→2, 3→4, 4→5
- 글자 화살표: 2 →(a) 3, 5 →(b) 6
- 시작 묶음: 1에서 ε으로 2, 4. 4에서 ε으로 5. \(T_0 = \{1, 2, 4, 5\}\).
- (\(T_0\), a): 2에서 a로 3. \(\epsilon\text{-}closure(3) = \{2, 3, 4, 5\}\). 처음 본다. \(T_1\).
- (\(T_0\), b): 5에서 b로 6. \(\{6\}\). 처음 본다. \(T_2\).
- (\(T_1\), a): 2에서 3. \(\{2, 3, 4, 5\} = T_1\). (\(T_1\), b): 5에서 6. \(T_2\).
- (\(T_2\), a)와 (\(T_2\), b): 6에서 나가는 화살표가 없다. 둘 다 \(\varnothing\).
- 멈춤 확인: 새 묶음이 없다.
- 받아들이는 상태와 전이 표: __
답
받아들이는 상태는 6이 든 \(T_2\) 하나다.
| a | b | |
|---|---|---|
| \(T_0\) | \(T_1\) | \(T_2\) |
| \(T_1\) | \(T_1\) | \(T_2\) |
| \(T_2\) | \(\varnothing\) | \(\varnothing\) |
NFA 상태 6개가 DFA 상태 3개가 되었다. \(T_0\)과 \(T_1\)은 표의 줄이 똑같다. 둘 다 “a를 더 읽거나 b를 읽으면 끝”인 자리다.
문제 3 · 하위목표 절반이 빈칸
“ab로 끝나는 줄”의 NFA다. \(p\)에서 a와 b로 \(p\), \(p\)에서 a로 \(q\), \(q\)에서 b로 \(r\). 시작 \(p\), 받아들이는 상태 \(r\).
- 시작 묶음: \(T_0 = \{p\}\).
- (\(T_0\), a): __
- (\(T_0\), b): \(\{p\} = T_0\).
- (\(T_1\), a): \(\{p, q\} = T_1\).
- (\(T_1\), b): __
- (\(T_2\), a)와 (\(T_2\), b): __
- 멈춤 확인: 새 묶음이 없다.
- 받아들이는 상태: __
답
- \(p\)에서 a로 \(p\)와 \(q\). \(\{p, q\}\). 처음 본다. \(T_1\).
- \(p\)에서 b로 \(p\), \(q\)에서 b로 \(r\). \(\{p, r\}\). 처음 본다. \(T_2\).
- (\(T_2\), a): \(p\)에서 \(p, q\). \(r\)은 갈 곳이 없다. \(\{p, q\} = T_1\). (\(T_2\), b): \(\{p\} = T_0\).
- \(r\)이 든 \(T_2\).
| a | b | |
|---|---|---|
| \(T_0\) | \(T_1\) | \(T_0\) |
| \(T_1\) | \(T_1\) | \(T_2\) |
| \(T_2\) | \(T_1\) | \(T_0\) |
문제 4 · 독립 문제
“뒤에서 두 번째 글자가 a인 줄”의 NFA다. \(s\)에서 a와 b로 \(s\), \(s\)에서 a로 \(t\), \(t\)에서 a와 b로 \(u\). 시작 \(s\), 받아들이는 상태 \(u\). 알파벳은 \(\{a, b\}\)다. (가) DFA의 묶음과 전이 표, 받아들이는 상태를 구하라. (나) NFA 상태 수와 DFA 상태 수를 견주고, “뒤에서 세 번째 글자가 a”로 바꾸면 각각 몇 개가 될지 예측하라.
답
(가) \(T_0 = \{s\}\), \(T_1 = \{s, t\}\), \(T_2 = \{s, t, u\}\), \(T_3 = \{s, u\}\). 받아들이는 상태는 \(u\)가 든 \(T_2\)와 \(T_3\).
| a | b | |
|---|---|---|
| \(T_0\) | \(T_1\) | \(T_0\) |
| \(T_1\) | \(T_2\) | \(T_3\) |
| \(T_2\) | \(T_2\) | \(T_3\) |
| \(T_3\) | \(T_1\) | \(T_0\) |
(나) NFA는 3개, DFA는 \(4 = 2^2\)개다. 세 번째로 바꾸면 NFA는 상태 하나만 늘어 4개, DFA는 \(8 = 2^3\)개다. DFA는 마지막 두 글자(또는 세 글자)가 각각 a였는지를 모두 기억해야 한다. 네 묶음이 바로 “마지막 두 글자가 bb, ba, aa, ab”인 네 경우다. NFA는 “지금 읽는 a가 뒤에서 두 번째일 것”이라고 찍기만 하면 되어서 작다.