목차
DFA
차례대로 유한 집합, 입력 문자, 상태 전이 함수, 초기 상태, 최종 상태 집합
DFA는 input symbol을 통해 전이될 수 있는 상태가 하나밖에 없다.
Q = {q1, q2, q3}
Σ = {0, 1}
q1: start state
F = {q2}
δ given by
| δ | 0 | 1 |
| q1 | q1 | q2 |
| q2 | q3 | q2 |
| q3 | q2 | q2 |
(상태 전이표)
여기서 만약 input symbol이 01011이라 해보자.
δ(q1, 0) = q1
δ(q1, 1) = q2
δ(q2, 0) = q3
δ(q3, 1) = q2
δ(q2, 1) = q2
최종 도달한 상태는 q2이며 이는 수락상태이다.
입력 01011의 경우 DFA의 최종 상태가 q2이므로 인식된다.
최종적으로 q2에 도달하지 않는 입력은 수락 상태가 되지 못 하는데, 수락상태가 되지 않는 입력 예시는 다음과 같다.
- 최종 상태 q1 예시 : 00
- δ(q1, 0) = q1
- δ(q1, 0) = q1
- 최종 상태 q3 예시 : 01010
- δ(q1, 0) = q1
- δ(q1, 1) = q2
- δ(q2, 0) = q3
- δ(q3, 1) = q2
- δ(q2, 0) = q3