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