Generalized NFA

상위 문서: Finite Automata

개요

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

Definition of GNFA

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

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

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

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

Acceptance by a GNFA

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

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

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

NFA to GNFA

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

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