Generalized NFA - 편집 역사

Pinkgo: /* Definition of GNFA */

2025-10-08T19:38:53Z

Definition of GNFA

← 이전 판		2025년 10월 8일 (수) 19:38 판
17번째 줄:		17번째 줄:
	* <math>q_{start}</math> is a "source".<ref>해당 상태에 대해 들어오는 간선이 없다는 것을 의미한다.</ref>		* <math>q_{start}</math> is a "source".<ref>해당 상태에 대해 들어오는 간선이 없다는 것을 의미한다.</ref>
	* <math>q_{end}</math> is a "sink".<ref>해당 상태에서 출발하는 간선이 없다는 것을 의미한다.</ref>		* <math>q_{end}</math> is a "sink".<ref>해당 상태에서 출발하는 간선이 없다는 것을 의미한다.</ref>
	* <math>q_{start},\,\, q_{end}</math> 외의 모든 상태 쌍 <math>(q, r)</math>에 대해 전이는 하나의 정규표현식으로 라벨링된다.		* <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)이다.		* 예외적으로, 어떤 GNFA에 대해 <math>Q = \{q_{start},\,\, q_{end}\}</math>라면, <math>q_{start} \rightarrow q_{accept}</math> 사이의 전이에 대한 라벨이 정규표현식 R이며, 이에 대한 언어는 L(R)이다.

Pinkgo: /* Definition of GNFA */

2025-10-08T19:38:15Z

Definition of GNFA

← 이전 판		2025년 10월 8일 (수) 19:38 판
13번째 줄:		13번째 줄:
	# <math>q_{start}</math>: 시작 상태		# <math>q_{start}</math>: 시작 상태
	# <math>q_{end}</math>: 종료 상태		# <math>q_{end}</math>: 종료 상태
	이때, 아래와 같은 제약이 ~~존재한다고 가정하자~~:		이때, 아래와 같은 제약이 존재한다:
	* <math>q_{start} \neq q_{accept}</math>		* <math>q_{start} \neq q_{accept}</math>
	* <math>q_{start}</math> is a "source".<ref>해당 상태에 대해 들어오는 간선이 없다는 것을 의미한다.</ref>		* <math>q_{start}</math> is a "source".<ref>해당 상태에 대해 들어오는 간선이 없다는 것을 의미한다.</ref>

Pinkgo: /* NFA to GNFA */

2025-09-29T15:52:33Z

NFA to GNFA

← 이전 판		2025년 9월 29일 (월) 15:52 판
30번째 줄:		30번째 줄:

	==NFA to GNFA==		==NFA to GNFA==
	[[파일:Figure 1. DFA example.png\|섬네일\|Figure 1. DFA example]]		[[파일:Figure 1. DFA example.png\|섬네일\|Figure 1. DFA example\|250x250픽셀]]
	GNFA는 기본적으로 전이가 정규표현식으로 라벨링된 NFA일 뿐이므로, NFA가 주어지면 그와 동치인 GNFA로 치환할 수 있다. 이때 치환을 하는 절차는 아래와 같다.		GNFA는 기본적으로 전이가 정규표현식으로 라벨링된 NFA일 뿐이므로, NFA가 주어지면 그와 동치인 GNFA로 치환할 수 있다. 이때 치환을 하는 절차는 아래와 같다.
	# [[파일:Figure 2. DFA to GNFA.png\|섬네일\|Figure 2. DFA to GNFA]]GNFA는 반드시 하나의 source와 하나의 sink를 가져야 하므로, <math>q_{start}</math>와 <math>q_{accept}</math>를 추가한다.		# [[파일:Figure 2. DFA to GNFA.png\|섬네일\|Figure 2. DFA to GNFA\|250x250픽셀]]GNFA는 반드시 하나의 source와 하나의 sink를 가져야 하므로, <math>q_{start}</math>와 <math>q_{accept}</math>를 추가한다.
	# <math>q_{start}</math>와 원래의 시작 상태에 대해 ε-transition을 한다.		# <math>q_{start}</math>와 원래의 시작 상태에 대해 ε-transition을 한다.
	#* 이는 <math>\delta(q_{start}, q_0)</math>와 같이 표현되며, 다른 상태로는 전이되지 않는다.		#* 이는 <math>\delta(q_{start}, q_0)</math>와 같이 표현되며, 다른 상태로는 전이되지 않는다.

Pinkgo: /* NFA to GNFA */

2025-09-29T15:51:53Z

NFA to GNFA

← 이전 판		2025년 9월 29일 (월) 15:51 판
30번째 줄:		30번째 줄:

	==NFA to GNFA==		==NFA to GNFA==
			[[파일:Figure 1. DFA example.png\|섬네일\|Figure 1. DFA example]]
	GNFA는 기본적으로 전이가 정규표현식으로 라벨링된 NFA일 뿐이므로, NFA가 주어지면 그와 동치인 GNFA로 치환할 수 있다. 이때 치환을 하는 절차는 아래와 같다.		GNFA는 기본적으로 전이가 정규표현식으로 라벨링된 NFA일 뿐이므로, NFA가 주어지면 그와 동치인 GNFA로 치환할 수 있다. 이때 치환을 하는 절차는 아래와 같다.
	# GNFA는 반드시 하나의 source와 하나의 sink를 가져야 하므로, <math>q_{start}</math>와 <math>q_{accept}</math>를 추가한다.		# [[파일:Figure 2. DFA to GNFA.png\|섬네일\|Figure 2. DFA to GNFA]]GNFA는 반드시 하나의 source와 하나의 sink를 가져야 하므로, <math>q_{start}</math>와 <math>q_{accept}</math>를 추가한다.
	# <math>q_{start}</math>와 원래의 시작 상태에 대해 ε-transition을 한다.		# <math>q_{start}</math>와 원래의 시작 상태에 대해 ε-transition을 한다.
	#* 이는 <math>\delta(q_{start}, q_0)</math>와 같이 표현되며, 다른 상태로는 전이되지 않는다.		#* 이는 <math>\delta(q_{start}, q_0)</math>와 같이 표현되며, 다른 상태로는 전이되지 않는다.

Pinkgo: /* Acceptance by a GNFA */

2025-09-29T01:25:45Z

Acceptance by a GNFA

@@ 28번째 줄: / 28번째 줄: @@
 *# <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>가 반드시 그 정규표현식이 표현하는 언어 안에 있어야 한다.
 ==각주==

Pinkgo: /* Definition of GNFA */

2025-09-29T01:15:55Z

Definition of GNFA

← 이전 판		2025년 9월 29일 (월) 01:15 판
19번째 줄:		19번째 줄:
	* <math>q_{start},\,\, q_{end}</math> 외의 모든 상태 쌍 <math>(q, r)</math>에 대해 전이는 하나의 정규표현식으로 라벨링된다.		* <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)이다.		* 예외적으로, 어떤 GNFA에 대해 <math>Q = \{q_{start},\,\, q_{end}\}</math>라면, <math>q_{start} \rightarrow q_{accept}</math> 사이의 전이에 대한 라벨이 정규표현식 R이며, 이에 대한 언어는 L(R)이다.
	~~<math></math>~~

	==Acceptance by a GNFA==		==Acceptance by a GNFA==

Pinkgo: 새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Finite Automata ==개요== Generalized NFA(GNFA)는 전이(transit)을 의미하는 화살표가 단일 문자 대신 정규표현식으로 라벨링된 NFA를 의미한다. ==Definition of GNFA== GNFA는 NFA를 확장한 개념이며, 아래와 같은 5-tuple로 정의된다: # $Q$ : 유한한 상태 집합 # $\Sig...$

2025-09-29T01:15:13Z

새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Finite Automata ==개요== Generalized NFA(GNFA)는 전이(transit)을 의미하는 화살표가 단일 문자 대신 정규표현식으로 라벨링된 NFA를 의미한다. ==Definition of GNFA== GNFA는 NFA를 확장한 개념이며, 아래와 같은 5-tuple로 정의된다: # <math>Q</math>: 유한한 상태 집합 # <math>\Sig...

새 문서

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[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)이다.
<math></math>

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

==각주==