일반화된 비결정적 유한 오토마타

일반화된 비결정적 유한 오토마타(줄여서 GNFA)는 전이에 알파벳의 기호뿐 아니라 정규 표현식도 붙을 수 있는 비결정적 오토마타이다.

정의

GNFA는 유한 오토마타를 정규 표현식으로 바꾸는 알고리즘에서 필요하다. 즉 GNFA는 전이가 정규 표현식으로 정의된 NFA이다. GNFA의 예는 다음과 같다.

예를 들어 상태 q₂에서 상태 q_f로 가는 전이가 있고, 이 전이에는 정규 표현식 a^∗ b가 붙어 있다. GNFA의 그 밖의 조건은 다음과 같다.

• 시작 상태 q₀에서 다른 모든 상태로 가는 전이가 있어야 한다. 그림에서도 상태 q₀에서 다른 모든 상태로 전이가 나간다.
• GNFA에는 수락 상태가 하나뿐이고, 다른 모든 상태에서 이 상태로 가는 전이가 있다. 그림에서 보듯 모든 상태에서 q_f로 가는 화살표가 있다.
• 시작 상태와 수락 상태는 같으면 안 된다. 따라서 GNFA의 상태는 적어도 2개이다.
• 시작 상태와 수락 상태를 제외한 나머지 모든 상태에서는 시작 상태와 수락 상태를 제외한 다른 모든 상태로 가는 전이가 있어야 한다. 자기 루프(상태 q_i에서 상태 q_i로 가는 전이)도 포함한다.

보통의 NFA를 GNFA로 바꾸기

NFA가 주어지면 GNFA로 바꾸는 것은 간단하다.

1. 새 시작 상태 q_s를 만들고 원래 시작 상태로 가는 ε 전이를 만든다.
2. 새 수락 상태 q_f를 만들고 원래의 모든 수락 상태에서 상태 q_f로 가는 ε 전이를 둔다. 원래 수락 상태는 보통 상태로 바꾼다.
3. 다중 전이가 있으면(즉 상태 q₁에서 기호 0으로도 기호 1로도 상태 q₂에 갈 수 있으면) 이 규칙들을 정규 표현식 하나로 합치고, 원래 기호들을 합집합 연산자로 묶는다(즉 화살표에 정규 표현식 0|1을 붙인다).
4. 정의에 따라 있어야 할 전이가 오토마타에 없으면 그 전이를 만들고 정규 표현식 ∅을 붙인다. 이런 전이는 절대 일어나지 않으므로 오토마타가 수락하는 언어는 바뀌지 않는다.

이 오토마타는 오토마타를 정규 표현식으로 바꾸는 데 쓸 수 있다.