GNFA

GNFA

• 보통의 NFA는 alphabet 이나 ε를 transition arrow의 label로 가진다.
• Generalized nondeterministic finite automata (GNFA)는 보통의 NFA와는 달리 regular expression을 transition arrow의 label로 가지는 NFA다.
  

GNFA의 형태

• 시작 상태는 다른 모든 state로는 갈 수 있는 arrow가 있지만, 다른 state로부터 받는 arrow는 없다.
• 통과 상태는 하나만 있어야하며, 모든 state로부터 arrow를 받아야 하지만 다른 state로 나가는 arrow는 없다.
• 시작 상태와 통과 상태는 같지 않다.
• 시작 상태와 통과 상태를 제외하고, 나머지 일반 상태들끼리 서로 arrow를 하나씩 받아야 하며, 자기 자신에게도 하나를 받아야한다.

DFA를 GNFA로 바꾸기

• 새로운 시작 상태를 추가하며, 기존 시작상태로 ε arrow를 보낸다.
• 새로운 통과 상태를 추가하며, 기존 통과 상태 대신 새로운 통과 상태만 통과 상태로 남게 한다. 이 과정에서 기존 통과 상태에서 새로운 통과상태로 ε arrow를 보낸다.
• 어떤 상태에서 같은 상태로 가는 arrow a,b가 있을 때, 둘을 합치고 a ∪ b로 표시한다.
• 마지막으로, 상태간 arrow가 없으면 그 사이에 ∅ arrow를 추가한다.

GNFA를 regular expression으로 바꾸기

• GNFA는 k개의 state를 가진다.
• 왜냐하면, GNFA는 필수로 시작 상태와 통과 상태를 가져야 하며, 일반 상태 하나 이상을 가져야 하므로 k > 2이다.
• k > 2면, k − 1개의 상태를 가지는 GNFA를 만들 수 있다. 이 과정은 상태가 2개가 될 때 까지 반복한다.
• k = 2면, GNFA는 하나의 arrow를 가진다. 그 arrow는 시작 상태에서 통과 상태로 간다.
• 이 arrow에 붙은 label은 regular expression과 같다.

• 여기서 중요한 것은 k > 2일 때 상태가 하나 줄어든 GNFA를 만드는 방법이다.

• 먼저 일반 상태 하나를 정한 뒤, repairing한다. reparing이 끝나도 여전히 language를 recognize해야 한다.

• 중요한 건, 일반 상태를 없애야 하며, 시작 상태나 통과 상태를 없애면 안된다.
  

• 다음 예시에서 qrip을 없애보자.

• qrip을 없애고 여전히 language를 recognize해야한다. 다시 말해 수순은 똑같아야한다.

• 이를 위해 qrip에 들어오는 arrow와 qrip에서 시작해서 다시 들어오는 arrow, 마지막으로 qrip에서 나가는 arrow에 대해서 처리를 해줘야 한다.

• 먼저, qrip으로 들어오는 R1을 concatenation한다. R1

• 그 후 qrip 자신에서 나가면서 들어오는 R2는 몇 번을 해도 상관 없으므로 *를 추가한 후 concatenation한다. R1R2*

• 그 후 qrip에서 나가는 R3를 concatenation한다. R1R2*R3

• 마지막으로 R4와 R1R2*R3의 나가는 상태와 들어가는 상태가 같으므로 union한다. R1R2*R3∪R4

이 과정을 겹치면 상태가 하나 줄었어도 이전과 같아진다.

실제로 바꾸는 과정