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}$ 가 반드시 그 정규표현식이 표현하는 언어 안에 있어야 한다.

GNFA는 기본적으로 전이가 정규표현식으로 라벨링된 NFA일 뿐이므로, NFA가 주어지면 그와 동치인 GNFA로 치환할 수 있다. 이때 치환을 하는 절차는 아래와 같다.

GNFA는 반드시 하나의 source와 하나의 sink를 가져야 하므로, $q_{s t a r t}$ 와 $q_{a c c e p t}$ 를 추가한다.
qstart와 원래의 시작 상태에 대해 ε-transition을 한다.
- 이는 $δ (q_{s t a r t}, q_{0})$ 와 같이 표현되며, 다른 상태로는 전이되지 않는다.
qaccept와 원래의 accept 상태 qj∈F에 대해 ε-transition을 한다.
- 이는 $\forall q_{j} \in F . δ (q_{s t a r t}, q_{j})$ 와 같이 표현되며, 다른 상태로는 전이되지 않는다.
중복 전이 제거: 같은 두 상태 사이에 전이가 여러개 있으면 합집합( $\cup$ )으로 묶어서 하나로 만든다.
존재하지 않는 전이는 $\emptyset$ 와 같이 표현한다.