GNFA에 대하여

 

 

 

---

GNFA에 대하여

Generalized NFA

---

 

 

 

오늘은 GNFA입니다. (하루에 다 써올리고 있지만)

 

 

1. GNFA란

 

일단 GNFA는 Generalized Transition Graph(GTG)로도 불리우는 아이입니다.

기본적으로 GNFA는 Regular Expression의 표시를 가지고 있지만, NFA인 녀석이에요.

 

무슨 뜻이냐?

NFA는 보통 transition을 표현할 때 하나의 기호(λ(람다)나 알파벳, 혹은 숫자)를 사용합니다. 그러나 GNFA는 그렇지 않고 Regular Expression처럼 일련의 기호를 사용합니다. 아래 보여지는 예시처럼요!

 

GNFA

 

아무튼 GNFA는 NFA와 Regular Expression의 그 어딘가에 있습니다.

그리고 당연히 NFA에는 무조건 대응하는 GNFA가 존재합니다. 대신 다음 조건을 지켜야 합니다.

 

1. GNFA로 만드려는 state들은 모두 accepting state와 starting state가 모두 아니여야함 2. GNFA는 NFA에서 중간에 존재하는 하나의 state를 줄여서 만들 수 있음(예시의 그림에서는 q제거)

 

예시

그럼 당연히 NFA를 Regular Expression으로 바꿀 때 사용이 되겠죠??

NFA를 RE로 바꾸는 건 따로 글을 작성할 예정이고, 이 글에서는 NFA를 GNFA로 바꾸는 방법 까지만 다뤄봅시다.

 

 

 

 

 

 

 

2. NFA to GNFA

 

위에서 사용한 예시를 직접 바꾸면서 방법론을 익혀봅시다. 1번에서 언급되었던 전제조건을 만족하기 위해 q_i, q, q_j는 모두 accepting state 및 starting state가 아니라는 가정을 합시다. 그리고 GNFA로 바꾸는 과정은 기본적으로 state 하나을 를 없애는 과정이기 때문에 3개만 들고 왔습니다.

우선 바꿀 NFA입니다. 

이 NFA를 GNFA로 바꾸기 위해서는 우선 4가지 케이스로 나누어 생각하면 됩니다.

 

1. qi에서 qi까지의 경로  2. qi에서 qj까지의 경로  3. qj에서 qi까지의 경로  4. qj에서 qj까지의 경로

 

그럼 다음과 같은 GNFA를 얻을 수 있습니다!

 

 

혹시 이런 질문을 가지고 있나요?

 

Q. q_i에서 q_i까지의 경로까지의 경로에서 경로 abcd는 포함 안되어있는거 아닌가요??

 

A. ae*b, ce*d로 구현할 수 있기 때문에 필요 없습니당

 

 

아무튼 단순하죠? 보통은 이 과정을 통해서 RE로 변환시킵니다. 이 과정은 다른 글을 작성하도록 할게요. 끝!