이번엔 DFA에서 State를 줄여나가는 방법이다. 먼저 state를 2개로 만든 모양이다. 빨간색 부분을 1구역, 파란색 부분을 2구역 이라고 보자. 1구역에는 A, B, D가 있고 2구역에는 C,E가 있다. ABD는 각각 a 일때 1구역에 머물러있고, b 일때는 A는 1로, 나머지는 2구역으로 이동한다. 표로 정리하면 이렇게 된다. a일 경우와 b가 같아야 한 state로 묶을 수 있으며, 현재 ABD state는 B,D경우가 다르므로 하나의 state로 만들 수 없다. 그러면 좀 더 쪼개서 3개의 state로 만들어보자. 구역을 3개로 나누어 보았다. 이렇게 되면 각 구역에서 선택지에 따라 일정한 곳으로 이동하게 된다. 이러한 식으로 정리가 가능하다. 그럼 각각 1, 2, 3을 다시 오토마타로 만들..

Non-Deterministic Finite Automata(NFA) 는 어디로 갈지 확실하게 정해지지 않은 오토마타이다. q0에서 선택지가 a일때 , q1일수도 있고 q2일수도 있다는 이야기이다. 그래서 이러한 NFA를 Deterministic Finite Automata(DFA)로 바꾸어야 하는게 목표이다. NFA의 예시 이와 같은 그림으로 나타낼 수 있다. 근데 경우의 수에 따라 화살표가 정해지지 않으니 좀 헷갈리는 부분들이 많이 있다. 이 오토마타에 1001을 입력하면 어떻게 될까?δ∪ 먼저 q0 에서 시작하기 때문에 δ({q0}, 1011) 에서 시작한다. 시작에서 1이면 q1또는 q3으로 갈 수 있다. δ({q1,q3}, 011) 가 된다. 이는 δ(q1, 11) ∪ δ(q2, 11)로도 표기..