Finite Automata - 편집 역사

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

2026-01-15T15:20:55Z

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

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

	상위 문서: [[계산 이론 개론#Finite Automata\|계산 이론 개론]]		상위 문서: [[계산 이론 개론#Finite Automata\|계산 이론 개론]]

Pinkgo: /* Formal Definition of Finite Automaton */

2025-10-26T04:56:31Z

Formal Definition of Finite Automaton

← 이전 판		2025년 10월 26일 (일) 04:56 판
31번째 줄:		31번째 줄:
	* <math>\Sigma</math>: 유한 입력 기호 집합(입력 알파벳)		* <math>\Sigma</math>: 유한 입력 기호 집합(입력 알파벳)
	* <math>\delta</math>: <math>Q\times \Sigma \rightarrow Q</math>: 전이 함수(transition function), 현재 상태와 입력 기호를 다음 상태로 매핑		* <math>\delta</math>: <math>Q\times \Sigma \rightarrow Q</math>: 전이 함수(transition function), 현재 상태와 입력 기호를 다음 상태로 매핑
	** <math>Q\times \Sigma</math>는 상탱 집합과 알파벳 집합의 모든 가능한 쌍이며, 전이 함수 <math>\delta</math>는 이 쌍을 받아서 새로운 상태로 매핑하는 역할을 한다. 이때 전이 함수는 모든 (state, input) 쌍에 대해 하나의 출력만 존재해야 한다. 따라서 결정적(deterministic)이라고 한다.		** <math>Q\times \Sigma</math>는 상태 집합과 알파벳 집합의 모든 가능한 쌍이며, 전이 함수 <math>\delta</math>는 이 쌍을 받아서 새로운 상태로 매핑하는 역할을 한다. 이때 전이 함수는 모든 (state, input) 쌍에 대해 하나의 출력만 존재해야 한다. 따라서 결정적(deterministic)이라고 한다.
	* <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)

Pinkgo: /* Equivalence of Automata */

2025-10-08T22:34:12Z

Equivalence of Automata

← 이전 판		2025년 10월 8일 (수) 22:34 판
57번째 줄:		57번째 줄:

	이때 NFA <math>N = (Q, \Sigma, \delta, q_0, F)</math>가 주어졌을 때, equivalent한 DFA M은:		이때 NFA <math>N = (Q, \Sigma, \delta, q_0, F)</math>가 주어졌을 때, equivalent한 DFA M은:
	* <math>N = (Q', \Sigma, \delta', q'_0, F')</math>		* <math>M = (Q', \Sigma, \delta', q'_0, F')</math>
	* <math>Q' = \mathcal{P}(Q)</math>: NFA 상태들의 모든 부분 집합		* <math>Q' = \mathcal{P}(Q)</math>: NFA 상태들의 모든 부분 집합
	* <math>F' = \{R\in Q' \| R \cap F \ne \emptyset\}</math>: Accept 상태가 포함된 부분 집합들		* <math>F' = \{R\in Q' \| R \cap F \ne \emptyset\}</math>: Accept 상태가 포함된 부분 집합들

Pinkgo: /* Equivalence of Automata */

2025-10-08T22:14:37Z

Equivalence of Automata

← 이전 판		2025년 10월 8일 (수) 22:14 판
75번째 줄:		75번째 줄:
	<math>q_1 = \{Q_1, Q_2, Q_3\}</math>		<math>q_1 = \{Q_1, Q_2, Q_3\}</math>
	이에 따라 figure 3의 다이어그램이 만들어진다. 이때 accept state가 <math>q_1</math>인 이유는 원래 NFA의 accept state인 <math>Q_3</math>를 포함하기 때문이다. 따라서 DFA의 유일한 수용 상태는 <math>q_1</math>이다. 또한 원래 <math>\{Q_1, Q_2, Q_3\}</math>의 부분집합은 총 8개 이지만, 실제로 도달할 수 있는 것은 <math>\{Q_1, Q_2\}, \{Q_1, Q_2, Q_3\}</math> 두개 뿐이므로 나머지 6개 집합은 reachable하지 않고 DFA에서 무시해도 된다.		이에 따라 figure 3의 다이어그램이 만들어진다. 이때 accept state가 <math>q_1</math>인 이유는 원래 NFA의 accept state인 <math>Q_3</math>를 포함하기 때문이다. 따라서 DFA의 유일한 수용 상태는 <math>q_1</math>이다. 또한 원래 <math>\{Q_1, Q_2, Q_3\}</math>의 부분집합은 총 8개 이지만, 실제로 도달할 수 있는 것은 <math>\{Q_1, Q_2\}, \{Q_1, Q_2, Q_3\}</math> 두개 뿐이므로 나머지 6개 집합은 reachable하지 않고 DFA에서 무시해도 된다.
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~



	==Other Ways to Model Computing Devices==		==Other Ways to Model Computing Devices==

Pinkgo: /* Formal Definition of Finite Automaton */

2025-10-08T12:56:48Z

Formal Definition of Finite Automaton

← 이전 판		2025년 10월 8일 (수) 12:56 판
35번째 줄:		35번째 줄:
	* <math>F \subseteq Q</math>: 수용 상태 집합(a set of accept states)		* <math>F \subseteq Q</math>: 수용 상태 집합(a set of accept states)
	이를 통해서 DFA M이 수용하는 어떤 문자열 집합 <math>w = w_1w_2\cdots w_n</math>일 때, <math>M = (Q, \Sigma, \delta, q_0, F)</math>이 <math>w</math>를 "수용"한다는 것은 아래와 같이 정의된다.		이를 통해서 DFA M이 수용하는 어떤 문자열 집합 <math>w = w_1w_2\cdots w_n</math>일 때, <math>M = (Q, \Sigma, \delta, q_0, F)</math>이 <math>w</math>를 "수용"한다는 것은 아래와 같이 정의된다.
	어떤 순열 <math>r_0r_1r_2\cdots r_n</math>이 존재하여 아래의 조건을 만족한다.		어떤 상태 순열(a sequence of states) <math>r_0r_1r_2\cdots r_n</math>이 존재하여 아래의 조건을 만족한다.
	1. 시작 상태: <math>r_0 = q_0</math>		1. 시작 상태: <math>r_0 = q_0</math>
	2. 각 단계에서 <math>\delta(r_i, w_{i+1}) = r_{i+1}, i = 0,1,\cdots,n-1</math>		2. 각 단계에서 <math>\delta(r_i, w_{i+1}) = r_{i+1}, i = 0,1,\cdots,n-1</math>

Pinkgo: /* Nondeterministic Finite Automata */

2025-09-29T00:52:20Z

Nondeterministic Finite Automata

← 이전 판		2025년 9월 29일 (월) 00:52 판
45번째 줄:		45번째 줄:
	==[[Nondeterministic Finite Automata]]==		==[[Nondeterministic Finite Automata]]==
	자세한 내용은 [[Nondeterministic Finite Automata]] 문서를 참조하십시오.		자세한 내용은 [[Nondeterministic Finite Automata]] 문서를 참조하십시오.

			==[[Generalized NFA]]==
			자세한 내용은 [[Generalized NFA]] 문서를 참조하십시오.

	==Equivalence of Automata==		==Equivalence of Automata==

Pinkgo: /* Equivalence of Automata */

2025-09-16T07:49:35Z

Equivalence of Automata

← 이전 판		2025년 9월 16일 (화) 07:49 판
60번째 줄:		60번째 줄:
	* <math>\delta'(R, a) = \bigcup_{r\in R}E(\delta(r,a))</math>: DFA에서의 전이는 NFA의 여러 전이를 동시에 고려한 집합		* <math>\delta'(R, a) = \bigcup_{r\in R}E(\delta(r,a))</math>: DFA에서의 전이는 NFA의 여러 전이를 동시에 고려한 집합
	이때 <math>E(R)</math>은 집합 R에서 시작해서 ε-transition만 따라갔을 때 도달 가능한 모든 상태를 의미한다. 이는 Powerset Construction에서 꼭 필요하다. 어떤 입력을 읽기 전에 미리 ε-transition으로 퍼질 수 있으니까, 이를 미리 포함해서 DFA 상태를 정의해야 하기 때문이다.		이때 <math>E(R)</math>은 집합 R에서 시작해서 ε-transition만 따라갔을 때 도달 가능한 모든 상태를 의미한다. 이는 Powerset Construction에서 꼭 필요하다. 어떤 입력을 읽기 전에 미리 ε-transition으로 퍼질 수 있으니까, 이를 미리 포함해서 DFA 상태를 정의해야 하기 때문이다.
			[[파일:Figure 2. NFA example.png\|섬네일\|Figure 2. NFA example]]
			[[파일:Figure 3. DFA example.png\|섬네일\|Figure 3. DFA example]]
			Figure 2의 NFA 다이어그램은 figure 3의 DFA 다이어그램으로 변경될 수 있다. Figure 2를 분석하면 아래와 같다:
			<math>q'_0 = E({Q_1}) = \{Q_1, Q_2\}</math>
			<math>\delta'(\{Q_1, Q_2\}, 0) = E(\{Q_1, Q_3\}) = \{Q_1, Q_2, Q_3\}</math>
			<math>\delta'(\{Q_1, Q_2\}, 1) = E(\{Q_1, Q_3\}) = \{Q_1, Q_2, Q_3\}</math>
			<math>\delta'(\{Q_1, Q_2, Q_3\}, 0) = E(\{Q_1, Q_3\}) = \{Q_1, Q_2, Q_3\}</math>
			<math>\delta'(\{Q_1, Q_2, Q_3\}, 1) = E(\{Q_1, Q_3\}) = \{Q_1, Q_2, Q_3\}</math>
			즉, DFA는 사실상 2개의 상태만 가진다:
			<math>q_0 = \{Q_1, Q_2\}</math>
			<math>q_1 = \{Q_1, Q_2, Q_3\}</math>
			이에 따라 figure 3의 다이어그램이 만들어진다. 이때 accept state가 <math>q_1</math>인 이유는 원래 NFA의 accept state인 <math>Q_3</math>를 포함하기 때문이다. 따라서 DFA의 유일한 수용 상태는 <math>q_1</math>이다. 또한 원래 <math>\{Q_1, Q_2, Q_3\}</math>의 부분집합은 총 8개 이지만, 실제로 도달할 수 있는 것은 <math>\{Q_1, Q_2\}, \{Q_1, Q_2, Q_3\}</math> 두개 뿐이므로 나머지 6개 집합은 reachable하지 않고 DFA에서 무시해도 된다.
	<math></math>		<math></math>
	<math></math>		<math></math>
66번째 줄:		78번째 줄:
	<math></math>		<math></math>
	<math></math>		<math></math>
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~

	==Other Ways to Model Computing Devices==		==Other Ways to Model Computing Devices==

Pinkgo: /* Nondeterministic Finite Automata */

2025-09-16T07:04:58Z

Nondeterministic Finite Automata

@@ 45번째 줄: / 45번째 줄: @@
 ==[[Nondeterministic Finite Automata]]==
 자세한 내용은 [[Nondeterministic Finite Automata]] 문서를 참조하십시오.
 ==Other Ways to Model Computing Devices==

Pinkgo: /* Formal Definition of Finite Automaton */

2025-09-16T06:22:13Z

Formal Definition of Finite Automaton

← 이전 판		2025년 9월 16일 (화) 06:22 판
29번째 줄:		29번째 줄:
	DFA(Deterministic Finite Automaton)은 아래와 같은 5-튜플(<math>Q, \Sigma, \delta, q_0, F</math>)로 정의할 수 있다:		DFA(Deterministic Finite Automaton)은 아래와 같은 5-튜플(<math>Q, \Sigma, \delta, q_0, F</math>)로 정의할 수 있다:
	* <math>Q</math>: 유한 상태 집합		* <math>Q</math>: 유한 상태 집합
	* <math>\Sigma</math>: 유한 입력 기호 집합		* <math>\Sigma</math>: 유한 입력 기호 집합(입력 알파벳)
	* <math>\delta</math>: <math>Q\times \Sigma \rightarrow Q</math>: 전이 함수(transition function), 현재 상태와 입력 기호를 다음 상태로 매핑		* <math>\delta</math>: <math>Q\times \Sigma \rightarrow Q</math>: 전이 함수(transition function), 현재 상태와 입력 기호를 다음 상태로 매핑
	** <math>Q\times \Sigma</math>는 상탱 집합과 알파벳 집합의 모든 가능한 쌍이며, 전이 함수 <math>\delta</math>는 이 쌍을 받아서 새로운 상태로 매핑하는 역할을 한다. 이때 전이 함수는 모든 (state, input) 쌍에 대해 하나의 출력만 존재해야 한다. 따라서 결정적(deterministic)이라고 한다.		** <math>Q\times \Sigma</math>는 상탱 집합과 알파벳 집합의 모든 가능한 쌍이며, 전이 함수 <math>\delta</math>는 이 쌍을 받아서 새로운 상태로 매핑하는 역할을 한다. 이때 전이 함수는 모든 (state, input) 쌍에 대해 하나의 출력만 존재해야 한다. 따라서 결정적(deterministic)이라고 한다.
	* <math>q_0 \in Q</math>: 시작 상태(start state)		* <math>q_0 \in Q</math>: 시작 상태(start state)
	* <math>F \subseteq Q</math>: 수용 상태 집합(accept states)		* <math>F \subseteq Q</math>: 수용 상태 집합(a set of accept states)
	이를 통해서 DFA M이 수용하는 어떤 문자열 집합 <math>w = w_1w_2\cdots w_n</math>일 때, <math>M = (Q, \Sigma, \delta, q_0, F)</math>이 <math>w</math>를 "수용"한다는 것은 아래와 같이 정의된다.		이를 통해서 DFA M이 수용하는 어떤 문자열 집합 <math>w = w_1w_2\cdots w_n</math>일 때, <math>M = (Q, \Sigma, \delta, q_0, F)</math>이 <math>w</math>를 "수용"한다는 것은 아래와 같이 정의된다.
	어떤 순열 <math>r_0r_1r_2\cdots r_n</math>이 존재하여 아래의 조건을 만족한다.		어떤 순열 <math>r_0r_1r_2\cdots r_n</math>이 존재하여 아래의 조건을 만족한다.

Pinkgo: /* Finite Automata as Language Recognizers */

2025-09-16T06:10:47Z

Finite Automata as Language Recognizers

← 이전 판		2025년 9월 16일 (화) 06:10 판
42번째 줄:		42번째 줄:
	<math>L(M) = \{w\in \Sigma^*\|M\,\, accepts\,\, w\}</math>		<math>L(M) = \{w\in \Sigma^*\|M\,\, accepts\,\, w\}</math>
	이러한 언어는 [[Regular Languages\|정규 언어(regular language)]]라고 정의된다. 정규 언어에 대한 자세한 내용은 [[Regular Languages]] 문서를 참조해 주십시오.		이러한 언어는 [[Regular Languages\|정규 언어(regular language)]]라고 정의된다. 정규 언어에 대한 자세한 내용은 [[Regular Languages]] 문서를 참조해 주십시오.

			==[[Nondeterministic Finite Automata]]==
			자세한 내용은 [[Nondeterministic Finite Automata]] 문서를 참조하십시오.

	==Other Ways to Model Computing Devices==		==Other Ways to Model Computing Devices==