7 - Regular Language (NFA)

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)로도 표기할 수 있다.

이 q1 1이면 q1,q3이고 q2가 1이면 갈곳이 없기때문에 q1 경우의 수만 생각한다.

그래서 다시 정리하면 δ({q1,q3}, 1)이고 이걸 또 δ(q1, 1) ∪ δ(q3, 1)로 바꾸면

마지막은 q1,q3,qf의 경우의 수가 나온다.

 

 

NFA to DFA

---

컴퓨터는 0과 1밖에 모르기 때문에 NFA를 알아들을 수 없다.

그래서 NFA를 DFA로 바꾸는 법을 알아보도록 하자

생각보다 간단하게 하나로 뭉탱이를 만들어 화살표를 하나로 쓰는것이다.

즉 아까 q0에서 0일때 q1 또는 q2 로 가는것을

q0 에서 0일때 {q1,q2}로 간다고 하여서 또는을 없애는 것이다.

 

와 같은 NFA 표가 있다고 하면

 

DFA로는 

와 같이 표현할 수 있다.

새로운 [q0,q1]을 만들어 이에 대한 경우의 수도 정의해 주는 것이다.

이런식으로 정의를 하면 0,1일때 또는이 등장하는 일은 없을것 이다.

 

기존의 NFA 

 

DFA 변환

이러한 식으로 0, 1일때 경우의 수가 무조건 하나가 된다.

여기서 q1은 접근할 일이 없기 때문에 사실상 의미가 없어져 버리는데, 결국 제거하게 된다.

하지만 점점 저러한 노드들이 늘어난다면 제거해야 할 노드도 많아지는데

다음엔 이에 대해서 알아보도록 하자