Generalized NFA

개요

Generalized NFA(GNFA)는 전이(transit)을 의미하는 화살표가 단일 문자 대신 정규표현식으로 라벨링된 NFA를 의미한다.

GNFA는 NFA를 확장한 개념이며, 아래와 같은 5-tuple로 정의된다:

이때, 아래와 같은 제약이 존재한다고 가정하자:

$q_{s t a r t} \neq q_{a c c e p t}$
$q_{s t a r t}$ is a "source".^[1]
$q_{e n d}$ is a "sink".^[2]
$q_{s t a r t}, q_{e n d}$ 외의 모든 상태 쌍 $(q, r)$ 에 대해 전이는 하나의 정규표현식으로 라벨링된다.
예외적으로, 어떤 GNFA에 대해 $Q = {q_{s t a r t}, q_{e n d}}$ 라면, $q_{s t a r t} \to q_{a c c e p t}$ 사이의 전이에 대한 라벨이 정규표현식 R이며, 이에 대한 언어는 L(R)이다.

GNFA가 $w \in Σ *$ 를 인식한다는 것은 아래의 조건을 만족하는 경우이다:

문자열 $w$ 를 $w_{1} w_{2} \dots w_{k}$ 와 같이 분해할 수 있다.
경로 q0,q1,⋯,qk가 존재하여
1. $q_{0} = q_{s t a r t}$
2. $q_{k} = q_{a c c e p t}$
3. $w_{i} \in L (R_{i}) s . t . R_{i} = δ (q_{i - 1}, q_{i})$

즉, 이는 전이가 단순 문자 대신 정규표현식 $R_{i}$ 로 라벨링되어 있기 때문에, 해당 전이를 통과할 때는 입력 문자열 조각 $w_{i}$ 가 반드시 그 정규표현식이 표현하는 언어 안에 있어야 한다.