Nondeterministic Finite Automata - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:22:55Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:22 판
1번째 줄:		1번째 줄:
	[[분류:계산 이론 개론]]		[[분류:계산 이론 개론]]
	~~[[분류:컴퓨터 공학]]~~

	상위 문서: [[Finite Automata#Nondeterministic Finite Automata\|Finite Automata]]		상위 문서: [[Finite Automata#Nondeterministic Finite Automata\|Finite Automata]]

Pinkgo: /* Closure under Union */

2025-09-16T08:15:18Z

Closure under Union

← 이전 판		2025년 9월 16일 (화) 08:15 판
39번째 줄:		39번째 줄:

	===Closure under Union===		===Closure under Union===
			[[파일:Figure 2. Closure under Union .png\|대체글=Figure 2. Closure under Union \|섬네일\|Figure 2. Closure under Union ]]
	증명해야 하는 것은 아래와 같다:		증명해야 하는 것은 아래와 같다:
	~~[[파일:Figure 2. Closure under Union .png\|대체글=Figure 2. Closure under Union \|섬네일\|Figure 2. Closure under Union ]]~~
	<math>\forall A_1, A_2.\,\, (A_1\,\, regular \land A_2\,\, regular) \Rightarrow (A_1 \cup A_2\,\, regular)</math>		<math>\forall A_1, A_2.\,\, (A_1\,\, regular \land A_2\,\, regular) \Rightarrow (A_1 \cup A_2\,\, regular)</math>
	# 이를 위해 <math>A_1, A_2</math>를 인식하는 NFA <math>N_1, N_2</math>가 있다고 가정하자.		# 이를 위해 <math>A_1, A_2</math>를 인식하는 NFA <math>N_1, N_2</math>가 있다고 가정하자.
49번째 줄:		49번째 줄:

	===Closure under Concatenation===		===Closure under Concatenation===
			[[파일:Figure 3. Closure under Concatenation.png\|섬네일\|Figure 3. Closure under Concatenation]]
	증명해야 하는 것은 아래와 같다:		증명해야 하는 것은 아래와 같다:
	~~[[파일:Figure 3. Closure under Concatenation.png\|섬네일\|Figure 3. Closure under Concatenation]]~~
	<math>\forall A_1, A_2.\,\, (A_1\,\, regular \land A_2\,\, regular) \Rightarrow (A_1 \circ A_2\,\, regular)</math>		<math>\forall A_1, A_2.\,\, (A_1\,\, regular \land A_2\,\, regular) \Rightarrow (A_1 \circ A_2\,\, regular)</math>
	# 이를 위해 <math>A_1, A_2</math>를 인식하는 NFA <math>N_1, N_2</math>가 있다고 가정하자.		# 이를 위해 <math>A_1, A_2</math>를 인식하는 NFA <math>N_1, N_2</math>가 있다고 가정하자.
60번째 줄:		60번째 줄:

	===Closure under Star===		===Closure under Star===
			[[파일:Figure 4. Closure under Star.png\|섬네일\|Figure 4. Closure under Star]]
	증명해야 하는 것은 아래와 같다:		증명해야 하는 것은 아래와 같다:
	~~[[파일:Figure 4. Closure under Star.png\|섬네일\|Figure 4. Closure under Star]]~~
	<math>A\circ A \subseteq A</math>		<math>A\circ A \subseteq A</math>
	# 이를 위해 <math>A</math>를 인식하는 NFA <math>N</math>이 있다고 가정하자.		# 이를 위해 <math>A</math>를 인식하는 NFA <math>N</math>이 있다고 가정하자.

Pinkgo: /* Proof for Closure */

2025-09-16T08:15:04Z

Proof for Closure

← 이전 판		2025년 9월 16일 (화) 08:15 판
36번째 줄:		36번째 줄:

	==Proof for Closure==		==Proof for Closure==
	~~[[파일:Figure 2. Closure under Union .png\|대체글=Figure 2. Closure under Union \|섬네일\|Figure 2. Closure under Union ]]~~
	NFA를 이용하여 정규 언어의 기본 연산 폐쇄성(closure)를 증명할 수 있다.		NFA를 이용하여 정규 언어의 기본 연산 폐쇄성(closure)를 증명할 수 있다.

	===Closure under Union===		===Closure under Union===
	증명해야 하는 것은 아래와 같다:		증명해야 하는 것은 아래와 같다:
			[[파일:Figure 2. Closure under Union .png\|대체글=Figure 2. Closure under Union \|섬네일\|Figure 2. Closure under Union ]]
	<math>\forall A_1, A_2.\,\, (A_1\,\, regular \land A_2\,\, regular) \Rightarrow (A_1 \cup A_2\,\, regular)</math>		<math>\forall A_1, A_2.\,\, (A_1\,\, regular \land A_2\,\, regular) \Rightarrow (A_1 \cup A_2\,\, regular)</math>
	# 이를 위해 <math>A_1, A_2</math>를 인식하는 NFA <math>N_1, N_2</math>가 있다고 가정하자.		# 이를 위해 <math>A_1, A_2</math>를 인식하는 NFA <math>N_1, N_2</math>가 있다고 가정하자.

Pinkgo: /* Proof for Closure */

2025-09-16T08:14:54Z

Proof for Closure

← 이전 판		2025년 9월 16일 (화) 08:14 판
36번째 줄:		36번째 줄:

	==Proof for Closure==		==Proof for Closure==
			[[파일:Figure 2. Closure under Union .png\|대체글=Figure 2. Closure under Union \|섬네일\|Figure 2. Closure under Union ]]
	NFA를 이용하여 정규 언어의 기본 연산 폐쇄성(closure)를 증명할 수 있다.		NFA를 이용하여 정규 언어의 기본 연산 폐쇄성(closure)를 증명할 수 있다.

49번째 줄:		50번째 줄:
	===Closure under Concatenation===		===Closure under Concatenation===
	증명해야 하는 것은 아래와 같다:		증명해야 하는 것은 아래와 같다:
			[[파일:Figure 3. Closure under Concatenation.png\|섬네일\|Figure 3. Closure under Concatenation]]
	<math>\forall A_1, A_2.\,\, (A_1\,\, regular \land A_2\,\, regular) \Rightarrow (A_1 \circ A_2\,\, regular)</math>		<math>\forall A_1, A_2.\,\, (A_1\,\, regular \land A_2\,\, regular) \Rightarrow (A_1 \circ A_2\,\, regular)</math>
	# 이를 위해 <math>A_1, A_2</math>를 인식하는 NFA <math>N_1, N_2</math>가 있다고 가정하자.		# 이를 위해 <math>A_1, A_2</math>를 인식하는 NFA <math>N_1, N_2</math>가 있다고 가정하자.
59번째 줄:		61번째 줄:
	===Closure under Star===		===Closure under Star===
	증명해야 하는 것은 아래와 같다:		증명해야 하는 것은 아래와 같다:
			[[파일:Figure 4. Closure under Star.png\|섬네일\|Figure 4. Closure under Star]]
	<math>A\circ A \subseteq A</math>		<math>A\circ A \subseteq A</math>
	# 이를 위해 <math>A</math>를 인식하는 NFA <math>N</math>이 있다고 가정하자.		# 이를 위해 <math>A</math>를 인식하는 NFA <math>N</math>이 있다고 가정하자.

Pinkgo: /* Formal Definition of the Language Recognized by NFA */

2025-09-16T08:12:22Z

Formal Definition of the Language Recognized by NFA

@@ 34번째 줄: / 34번째 줄: @@
 ** <math>r_n \in F</math> (accept 상태 도달)
 이를 만족하는 모든 문자열들의 집합이 <math>L(M)</math>이다.
 ==각주==

Pinkgo: /* NFA Vs. DFA */

2025-09-16T07:52:58Z

NFA Vs. DFA

← 이전 판		2025년 9월 16일 (화) 07:52 판
9번째 줄:		9번째 줄:
	==NFA Vs. DFA==		==NFA Vs. DFA==
	DFA(Deterministic Finite Automata)에서는 각 상태와 입력 심볼 쌍 (q, a)에 대해 오직 하나의 전이만 정의된다. 하지만 NFA에서는 하나의 (q,a)에 대해 여러 개의 전이가 있을 수도 있고, 전이가 전혀 없을 수도 있으며, 입력을 소모하지 않고 이동하는 ε-transition도 허용된다. 이때 수용(accept) 조건은 어떤 행운의 선택(lucky choice)"의 전이 경로라도 최종 상태에 도달하면 문자열을 accept하는 것이다.		DFA(Deterministic Finite Automata)에서는 각 상태와 입력 심볼 쌍 (q, a)에 대해 오직 하나의 전이만 정의된다. 하지만 NFA에서는 하나의 (q,a)에 대해 여러 개의 전이가 있을 수도 있고, 전이가 전혀 없을 수도 있으며, 입력을 소모하지 않고 이동하는 ε-transition도 허용된다. 이때 수용(accept) 조건은 어떤 행운의 선택(lucky choice)"의 전이 경로라도 최종 상태에 도달하면 문자열을 accept하는 것이다.
			[[파일:Figure 1. NFA example .png\|가운데\|섬네일\|500x500픽셀\|Figure 1. NFA example ]]
	이는 figure 1을 통해 설명할 수 있다. 주어진 NFA는 {0,1} 위의 문자열을 입력받아, 끝에서 세 번째 문자가 1인 문자열을 accept한다. 이러한 NFA는 아래와 같은 방식으로 작동한다:		이는 figure 1을 통해 설명할 수 있다. 주어진 NFA는 {0,1} 위의 문자열을 입력받아, 끝에서 세 번째 문자가 1인 문자열을 accept한다. 이러한 NFA는 아래와 같은 방식으로 작동한다:
	# 계속해서 Q1에서 입력을 소비하다가,		# 계속해서 Q1에서 입력을 소비하다가,

Pinkgo: /* Formal Definition of the Language Recognized by NFA */

2025-09-16T06:36:18Z

Formal Definition of the Language Recognized by NFA

← 이전 판		2025년 9월 16일 (화) 06:36 판
29번째 줄:		29번째 줄:
	문자열 <math>w \in \Sigma*</math>를 NFA <math>M</math>이 accept한다는 것은 아래와 같이 정의된다:		문자열 <math>w \in \Sigma*</math>를 NFA <math>M</math>이 accept한다는 것은 아래와 같이 정의된다:
	* <math>w</math>를 <math>w=y_1y_2\cdots y_n</math>(각 <math>y_i\in \Sigma \cup \{\epsilon\}</math>)로 분해가능하고,		* <math>w</math>를 <math>w=y_1y_2\cdots y_n</math>(각 <math>y_i\in \Sigma \cup \{\epsilon\}</math>)로 분해가능하고,
	* 상태열 <math>r_0,r_1,\cdots,\r_n</math>이 존재하여:		* 상태열 <math>r_0,r_1,\cdots,r_n</math>이 존재하여:
	** <math>r_0=q_0</math> (시작 상태)		** <math>r_0=q_0</math> (시작 상태)
	** <math>r_{i+1} \in \delta(r_i, y_{i+1})</math> (전이 규칙을 따름)		** <math>r_{i+1} \in \delta(r_i, y_{i+1})</math> (전이 규칙을 따름)

Pinkgo: /* Formal Definition of NFA */

2025-09-16T06:35:56Z

Formal Definition of NFA

← 이전 판		2025년 9월 16일 (화) 06:35 판
25번째 줄:		25번째 줄:
	* <math>q_0 \in Q</math>: 시작 상태(start state)		* <math>q_0 \in Q</math>: 시작 상태(start state)
	* <math>F \subseteq Q</math>: 수용 상태 집합(a set of accept states)		* <math>F \subseteq Q</math>: 수용 상태 집합(a set of accept states)

			==Formal Definition of the Language Recognized by NFA==
			문자열 <math>w \in \Sigma*</math>를 NFA <math>M</math>이 accept한다는 것은 아래와 같이 정의된다:
			* <math>w</math>를 <math>w=y_1y_2\cdots y_n</math>(각 <math>y_i\in \Sigma \cup \{\epsilon\}</math>)로 분해가능하고,
			* 상태열 <math>r_0,r_1,\cdots,\r_n</math>이 존재하여:
			** <math>r_0=q_0</math> (시작 상태)
			** <math>r_{i+1} \in \delta(r_i, y_{i+1})</math> (전이 규칙을 따름)
			** <math>r_n \in F</math> (accept 상태 도달)
			이를 만족하는 모든 문자열들의 집합이 <math>L(M)</math>이다.

	==각주==		==각주==

Pinkgo: 새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Finite Automata ==개요== 해당 문서는 finite automata의 한 종류인 NFA(Nondeterministic Finite Automata)에 대해 설명하고, 이를 이용한 정규 언어의 정의 방식을 설명한다. ==NFA Vs. DFA== DFA(Deterministic Finite Automata)에서는 각 상태와 입력 심볼 쌍 (q, a)에 대해 오직 하나의 전이만 정의된다...

2025-09-16T06:26:01Z

새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Finite Automata ==개요== 해당 문서는 finite automata의 한 종류인 NFA(Nondeterministic Finite Automata)에 대해 설명하고, 이를 이용한 정규 언어의 정의 방식을 설명한다. ==NFA Vs. DFA== DFA(Deterministic Finite Automata)에서는 각 상태와 입력 심볼 쌍 (q, a)에 대해 오직 하나의 전이만 정의된다...

새 문서

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]

상위 문서: [[Finite Automata#Nondeterministic Finite Automata|Finite Automata]]

==개요==
해당 문서는 finite automata의 한 종류인 NFA(Nondeterministic Finite Automata)에 대해 설명하고, 이를 이용한 정규 언어의 정의 방식을 설명한다.

==NFA Vs. DFA==
DFA(Deterministic Finite Automata)에서는 각 상태와 입력 심볼 쌍 (q, a)에 대해 오직 하나의 전이만 정의된다. 하지만 NFA에서는 하나의 (q,a)에 대해 여러 개의 전이가 있을 수도 있고, 전이가 전혀 없을 수도 있으며, 입력을 소모하지 않고 이동하는 ε-transition도 허용된다. 이때 수용(accept) 조건은 어떤 행운의 선택(lucky choice)"의 전이 경로라도 최종 상태에 도달하면 문자열을 accept하는 것이다.

이는 figure 1을 통해 설명할 수 있다. 주어진 NFA는 {0,1} 위의 문자열을 입력받아, 끝에서 세 번째 문자가 1인 문자열을 accept한다. 이러한 NFA는 아래와 같은 방식으로 작동한다:
# 계속해서 Q1에서 입력을 소비하다가,
# 어느 순간 "여기가 끝에서 세 번째 자리일 것"이라고 추측(guess)하고 Q2로 이동.
# 그 뒤 정확히 두 개 문자를 더 읽고 Q4에 도착하면 accept.
# 만약 모든 "선택과 추측"이 실패하면, 해당 문자열을 수용되지 않음

==Formal Definition of NFA==
NFA는 DFA 처럼 아래와 같은 5-튜플로 정의된다:
* <math>Q</math>: 유한 상태 집합
* <math>\Sigma</math>: 유한 입력 기호 집합(입력 알파벳)
* <math>\delta</math>: <math>Q\times (\Sigma \cup \{\epsilon\} \rightarrow \mathcal{P}(Q))</math>: 전이 함수(transition function)
** 이는 DFA의 그것과는 다르게 “다음 상태 하나”가 아니라 “가능한 다음 상태들의 집합”을 반환한다.
** ε-transition이 발행하여 입력 문자를 읽지 않고도 상태가 바뀔 수 있다.
* <math>q_0 \in Q</math>: 시작 상태(start state)
* <math>F \subseteq Q</math>: 수용 상태 집합(a set of accept states)

==각주==