Generalized NFA 문서 원본 보기

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[Finite Automata#Generalized NFA|Finite Automata]]

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

==Definition of GNFA==
GNFA는 NFA를 확장한 개념이며, 아래와 같은 5-tuple로 정의된다:
# <math>Q</math>: 유한한 상태 집합
# <math>\Sigma</math>: 입력 알파벳
# <math>\delta</math>: 전이함수, 이때 전이는 정규 표현식을 통해 라벨링된다.
# <math>q_{start}</math>: 시작 상태
# <math>q_{end}</math>: 종료 상태
이때, 아래와 같은 제약이 존재한다고 가정하자:
* <math>q_{start} \neq q_{accept}</math>
* <math>q_{start}</math> is a "source".<ref>해당 상태에 대해 들어오는 간선이 없다는 것을 의미한다.</ref>
* <math>q_{end}</math> is a "sink".<ref>해당 상태에서 출발하는 간선이 없다는 것을 의미한다.</ref>
* <math>q_{start},\,\, q_{end}</math> 외의 모든 상태 쌍 <math>(q, r)</math>에 대해 전이는 하나의 정규표현식으로 라벨링된다.
* 예외적으로, 어떤 GNFA에 대해 <math>Q = \{q_{start},\,\, q_{end}\}</math>라면, <math>q_{start} \rightarrow q_{accept}</math> 사이의 전이에 대한 라벨이 정규표현식 R이며, 이에 대한 언어는 L(R)이다.

==Acceptance by a GNFA==
GNFA가 <math>w \in \Sigma*</math>를 인식한다는 것은 아래의 조건을 만족하는 경우이다:
* 문자열 <math>w</math>를 <math>w_1w_2\cdots w_k</math>와 같이 분해할 수 있다.
* 경로 <math>q_0,q_1,\cdots, q_k</math>가 존재하여
*# <math>q_0 = q_{start}</math>
*# <math>q_k = q_{accept}</math>
*# <math>w_i \in L(R_i)\,\,s.t.\,\, R_i = \delta(q_{i-1}, q_i)</math>
즉, 이는 전이가 단순 문자 대신 정규표현식 <math>R_i</math>로 라벨링되어 있기 때문에, 해당 전이를 통과할 때는 입력 문자열 조각 <math>w_i</math>가 반드시 그 정규표현식이 표현하는 언어 안에 있어야 한다.

==각주==