Generalized NFA

상위 문서: Finite Automata

개요

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

Definition of GNFA

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

1. $Q$: 유한한 상태 집합
2. $\mathrm{\Sigma }$: 입력 알파벳
3. $\delta$: 전이함수, 이때 전이는 정규 표현식을 통해 라벨링된다.
4. $q_{start}$: 시작 상태
5. $q_{end}$: 종료 상태

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

• $q_{start}\ne q_{accept}$
• $q_{start}$ is a "source".
• $q_{end}$ is a "sink".
• $q_{start},q_{end}$ 외의 모든 상태 쌍 $(q,r)$에 대해 전이는 하나의 정규표현식으로 라벨링된다.
• 예외적으로, 어떤 GNFA에 대해 $Q=\{q_{start},q_{end}\}$라면, $q_{start}\to q_{accept}$ 사이의 전이에 대한 라벨이 정규표현식 R이며, 이에 대한 언어는 L(R)이다.

Acceptance by a GNFA

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

• 문자열 $w$를 $w_1{w}_2\cdots w_k$와 같이 분해할 수 있다.
• 경로 $q_0,q_1,\cdots ,q_k$가 존재하여
  1. $q_0=q_{start}$
  2. $q_k=q_{accept}$
  3. $w_i\in L(R_i)s.t.R_i=\delta (q_{i-1},q_i)$

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

NFA to GNFA

Figure 1. DFA example

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

1. 

   Figure 2. DFA to GNFA

   GNFA는 반드시 하나의 source와 하나의 sink를 가져야 하므로, $q_{start}$와 $q_{accept}$를 추가한다.
2. $q_{start}$와 원래의 시작 상태에 대해 ε-transition을 한다.
   • 이는 $\delta (q_{start},q_0)$와 같이 표현되며, 다른 상태로는 전이되지 않는다.
3. $q_{accept}$와 원래의 accept 상태 $q_j\in F$에 대해 ε-transition을 한다.
   • 이는 $\mathrm{\forall }{q}_j\in F.\delta (q_{start},q_j)$와 같이 표현되며, 다른 상태로는 전이되지 않는다.
4. 중복 전이 제거: 같은 두 상태 사이에 전이가 여러개 있으면 합집합($\cup$)으로 묶어서 하나로 만든다.
5. 존재하지 않는 전이는 $\mathrm{\varnothing }$와 같이 표현한다.