Pushdown Automaton - 편집 역사

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

2026-01-15T15:23:45Z

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

← 이전 판		2026년 1월 15일 (목) 15:23 판
1번째 줄:		1번째 줄:
	[[분류:계산 이론 개론]]		[[분류:계산 이론 개론]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[Grammars#Context-Free Languages\|Context-Free Languages]]		상위 문서: [[Grammars#Context-Free Languages\|Context-Free Languages]]

Pinkgo: /* Definition of G */

2025-11-13T06:08:41Z

Definition of G

← 이전 판		2025년 11월 13일 (목) 06:08 판
97번째 줄:		97번째 줄:
	# 시작 변수: <math>S = A_{q_0q_{accept}}</math><ref>PDA의 시작 상태 <math>q_0</math>에서 accept 상태까지 가는 문자열을 생성해야 하므로, 문법의 시작기호는 이렇게 설정됩니다.</ref>		# 시작 변수: <math>S = A_{q_0q_{accept}}</math><ref>PDA의 시작 상태 <math>q_0</math>에서 accept 상태까지 가는 문자열을 생성해야 하므로, 문법의 시작기호는 이렇게 설정됩니다.</ref>
	# 생성 규칙: “u를 스택에 넣고 다시 꺼내는 과정 사이에 있는 계산 전체”를 문법 규칙 하나로 표현한다:		# 생성 규칙: “u를 스택에 넣고 다시 꺼내는 과정 사이에 있는 계산 전체”를 문법 규칙 하나로 표현한다:
	## <math>(r,u)\in delta(p,a,\epsilon) \land (q,\epsilon) \in \delta(s,b,u)</math>이면 <math>A_{pq} \rightarrow aA_{rs}b</math>이다.<ref>p에서 q로 가는 계산은 a를 읽고 u를 푸시한 뒤, 중간에 r에서 s로 이동하면서 u를 팝하며 b를 읽는다는 것을 나타낸다.</ref>		## <math>(r,u)\in \delta(p,a,\epsilon) \land (q,\epsilon) \in \delta(s,b,u)</math>이면 <math>A_{pq} \rightarrow aA_{rs}b</math>이다.<ref>p에서 q로 가는 계산은 a를 읽고 u를 푸시한 뒤, 중간에 r에서 s로 이동하면서 u를 팝하며 b를 읽는다는 것을 나타낸다.</ref>
	## <math>A_{pr} \rightarrow A_{pq}A_{qr}</math>		## <math>A_{pr} \rightarrow A_{pq}A_{qr}</math>
	## <math>A_{pp} \rightarrow \epsilon</math><ref>같은 상태에서 아무 동작 없이 스택이 빈 경우이다.</ref>		## <math>A_{pp} \rightarrow \epsilon</math><ref>같은 상태에서 아무 동작 없이 스택이 빈 경우이다.</ref>

Pinkgo: /* Definition of G */

2025-11-13T06:07:59Z

Definition of G

← 이전 판		2025년 11월 13일 (목) 06:07 판
95번째 줄:		95번째 줄:
	# 변수 집합: <math>V = \{A_{pq}\|p,q \in Q\}</math>		# 변수 집합: <math>V = \{A_{pq}\|p,q \in Q\}</math>
	#* 각 변수는 PDA의 상태 p에서 시작해, 상태 q에서 끝나는 모든 문자열들을 생성하는 비단말기를 의미한다.<ref>쉽게 말하면, “상태 p에서 시작해서 q로 갈 수 있는 입력 문자열”을 대표하는 문법 기호이다.</ref><ref>다르게 설명하면, 상태 p에서 상태 q로 이동하는 과정에서 스택의 상태가 처음과 같게 유지되는 모든 문자열들의 집합을 의미한다.</ref>		#* 각 변수는 PDA의 상태 p에서 시작해, 상태 q에서 끝나는 모든 문자열들을 생성하는 비단말기를 의미한다.<ref>쉽게 말하면, “상태 p에서 시작해서 q로 갈 수 있는 입력 문자열”을 대표하는 문법 기호이다.</ref><ref>다르게 설명하면, 상태 p에서 상태 q로 이동하는 과정에서 스택의 상태가 처음과 같게 유지되는 모든 문자열들의 집합을 의미한다.</ref>
	# 시작 변수: <math>S = A_{~~q_0,q_~~{accept}}</math><ref>PDA의 시작 상태 <math>q_0</math>에서 accept 상태까지 가는 문자열을 생성해야 하므로, 문법의 시작기호는 이렇게 설정됩니다.</ref>		# 시작 변수: <math>S = A_{q_0q_{accept}}</math><ref>PDA의 시작 상태 <math>q_0</math>에서 accept 상태까지 가는 문자열을 생성해야 하므로, 문법의 시작기호는 이렇게 설정됩니다.</ref>
	# 생성 규칙: “u를 스택에 넣고 다시 꺼내는 과정 사이에 있는 계산 전체”를 문법 규칙 하나로 표현한다:		# 생성 규칙: “u를 스택에 넣고 다시 꺼내는 과정 사이에 있는 계산 전체”를 문법 규칙 하나로 표현한다:
	## <math>(r,u)\in delta(p,a,\epsilon) \land (q,\epsilon) \in \delta(s,b,u)</math>이면 <math>A_{pq} \rightarrow aA_{rs}b</math>이다.<ref>p에서 q로 가는 계산은 a를 읽고 u를 푸시한 뒤, 중간에 r에서 s로 이동하면서 u를 팝하며 b를 읽는다는 것을 나타낸다.</ref>		## <math>(r,u)\in delta(p,a,\epsilon) \land (q,\epsilon) \in \delta(s,b,u)</math>이면 <math>A_{pq} \rightarrow aA_{rs}b</math>이다.<ref>p에서 q로 가는 계산은 a를 읽고 u를 푸시한 뒤, 중간에 r에서 s로 이동하면서 u를 팝하며 b를 읽는다는 것을 나타낸다.</ref>

Pinkgo: /* Formal Definition of nondeterministic PDA */

2025-11-13T05:41:20Z

Formal Definition of nondeterministic PDA

← 이전 판		2025년 11월 13일 (목) 05:41 판
19번째 줄:		19번째 줄:
	* <math>\Sigma</math>: 입력 알파벳		* <math>\Sigma</math>: 입력 알파벳
	* <math>\Gamma</math>: 스택 알파벳		* <math>\Gamma</math>: 스택 알파벳
	* <math>\delta</math>: ~~<math>Q\times \Sigma \rightarrow Q</math>: 전이 함수(transition function), 현재 상태와 입력 기호를 다음 상태로 매핑~~		* <math>\delta</math>: <math>\delta: Q\times \Sigma_\epsilon \times \Gamma_\epsilon \rightarrow P(Q\times \Gamma_\epsilon)</math>
	** <math>\delta: Q\times \Sigma_\epsilon \times \Gamma_\epsilon \rightarrow P(Q\times \Gamma_\epsilon)</math>		** 전이 함수(transition function)로, 현재 상태와 입력 기호를 다음 상태로 매핑한다.
	** 현재 상태, 입력 알파벳, 스택의 top 알파벳에 따라 여러 <math>(r,b) \in \delta(q,w,a)</math> 쌍을 반환한다.		** 현재 상태, 입력 알파벳, 스택의 top 알파벳에 따라 여러 <math>(r,b) \in \delta(q,w,a)</math> 쌍을 반환한다.
	* <math>q_0 \in Q</math>: 시작 상태(start state)		* <math>q_0 \in Q</math>: 시작 상태(start state)

Pinkgo: /* PDA's states */

2025-11-03T02:21:22Z

PDA's states

← 이전 판		2025년 11월 3일 (월) 02:21 판
66번째 줄:		66번째 줄:
	====PDA's states====		====PDA's states====
	CFG에서 만든 PDA는 아래와 같은 세 가지 핵심적인 상태를 가진다:		CFG에서 만든 PDA는 아래와 같은 세 가지 핵심적인 상태를 가진다:
	# <math>~~q_start~~</math>: 시작 상태		# <math>q_{start}</math>: 시작 상태
	#* 스택에 <math>$S</math>를 push한다.<ref><math>S</math>는 시작 비단말이고, $는 스택의 바닥을 표시한다.</ref>		#* 스택에 <math>$S</math>를 push한다.<ref><math>S</math>는 시작 비단말이고, $는 스택의 바닥을 표시한다.</ref>
	#* 다음 상태는 <math>q_{loop}</math>이다.		#* 다음 상태는 <math>q_{loop}</math>이다.
75번째 줄:		75번째 줄:
	# <math>q_{accept}</math>: Accept 상태		# <math>q_{accept}</math>: Accept 상태
	#* 스택이 완전히 비고 입력이 끝난 상태이다.		#* 스택이 완전히 비고 입력이 끝난 상태이다.
	이때 만약 여러 symbol을 한꺼번에 push해야 할 때는, “extra states”를 임시로 만들어 연속 push를 구현한다.		이때 만약 여러 symbol을 한꺼번에 push해야 할 때는, “extra states”를 임시로 만들어 연속 push를 구현한다.

	====PDA from CFG Example====		====PDA from CFG Example====

2025년 10월 30일 (목) 04:43에 Pinkgo님의 편집

2025-10-30T04:43:46Z

← 이전 판		2025년 10월 30일 (목) 04:43 판
1번째 줄:		1번째 줄:
	[[분류:계산 이론 개론]]		[[분류:계산 이론 개론]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]
	상위 문서: [[Grammars#Context-Free Languages~~#Pushdown Automaton~~\|Context-Free Languages]]		상위 문서: [[Grammars#Context-Free Languages\|Context-Free Languages]]

	==개요==		==개요==

Pinkgo: /* Definition of G */

2025-10-30T04:31:54Z

Definition of G

← 이전 판		2025년 10월 30일 (목) 04:31 판
94번째 줄:		94번째 줄:
	위의 내용을 사용하여 CFG를 구체적으로 아래와 같이 정의한다:		위의 내용을 사용하여 CFG를 구체적으로 아래와 같이 정의한다:
	# 변수 집합: <math>V = \{A_{pq}\|p,q \in Q\}</math>		# 변수 집합: <math>V = \{A_{pq}\|p,q \in Q\}</math>
	#* 각 변수는 PDA의 상태 p에서 시작해, 상태 q에서 끝나는 모든 문자열들을 생성하는 비단말기를 의미한다.<ref>쉽게 말하면, “상태 p에서 시작해서 q로 갈 수 있는 입력 문자열”을 대표하는 문법 기호이다.</ref>		#* 각 변수는 PDA의 상태 p에서 시작해, 상태 q에서 끝나는 모든 문자열들을 생성하는 비단말기를 의미한다.<ref>쉽게 말하면, “상태 p에서 시작해서 q로 갈 수 있는 입력 문자열”을 대표하는 문법 기호이다.</ref><ref>다르게 설명하면, 상태 p에서 상태 q로 이동하는 과정에서 스택의 상태가 처음과 같게 유지되는 모든 문자열들의 집합을 의미한다.</ref>
	# 시작 변수: <math>S = A_{q_0,q_{accept}}</math><ref>PDA의 시작 상태 <math>q_0</math>에서 accept 상태까지 가는 문자열을 생성해야 하므로, 문법의 시작기호는 이렇게 설정됩니다.</ref>		# 시작 변수: <math>S = A_{q_0,q_{accept}}</math><ref>PDA의 시작 상태 <math>q_0</math>에서 accept 상태까지 가는 문자열을 생성해야 하므로, 문법의 시작기호는 이렇게 설정됩니다.</ref>
	# 생성 규칙: “u를 스택에 넣고 다시 꺼내는 과정 사이에 있는 계산 전체”를 문법 규칙 하나로 표현한다:		# 생성 규칙: “u를 스택에 넣고 다시 꺼내는 과정 사이에 있는 계산 전체”를 문법 규칙 하나로 표현한다:

Pinkgo: /* CFG from PDA Example */

2025-10-30T04:30:33Z

CFG from PDA Example

← 이전 판		2025년 10월 30일 (목) 04:30 판
107번째 줄:		107번째 줄:
	<math>A_{14}\rightarrow A_{23}</math> ($를 push한 후, $를 pop)		<math>A_{14}\rightarrow A_{23}</math> ($를 push한 후, $를 pop)
	<math>A_{23}\rightarrow 0A_{23}1</math> (0을 push한 후, 0을 pop)		<math>A_{23}\rightarrow 0A_{23}1</math> (0을 push한 후, 0을 pop)
	<math>A_{23}\rightarrow 0A_{33}1</math> (0을 push한 후, 0을 pop)		<math>A_{23}\rightarrow 0A_{22}1</math> (0을 push한 후, 0을 pop)
	<math>A_{33}\rightarrow \epsilon</math>		<math>A_{22}\rightarrow \epsilon</math>
	위에서 <math>A_{14}</math>는 PDA의 시작 상태 <math>q_1</math>에서 accept 상태 <math>q_4</math>까지 가는 모든 입력 문자열을 생성하는 비단말기이다. 따라서 해당 비단말기는 주어진 PDA가 인식하는 언어 전체를 생성해야 하므로 <math>S=A_{14}</math>가 PDA로부터 정의되는 문법의 시작 기호 역할을 한다.		위에서 <math>A_{14}</math>는 PDA의 시작 상태 <math>q_1</math>에서 accept 상태 <math>q_4</math>까지 가는 모든 입력 문자열을 생성하는 비단말기이다. 따라서 해당 비단말기는 주어진 PDA가 인식하는 언어 전체를 생성해야 하므로 <math>S=A_{14}</math>가 PDA로부터 정의되는 문법의 시작 기호 역할을 한다.

	<math>A_{14}\rightarrow A_{23}</math>과 같은 규칙은 아래의 두 전이		<math>A_{14}\rightarrow A_{23}</math>과 같은 규칙은 아래의 두 전이:
	<math>(q_1,\epsilon,\epsilon)\rightarrow (q_2,$)</math>		<math>(q_1,\epsilon,\epsilon)\rightarrow (q_2,$)</math>
	<math>(q_3,\epsilon,$)\rightarrow (q_4,\epsilon)</math>		<math>(q_3,\epsilon,$)\rightarrow (q_4,\epsilon)</math>
	을 $에 대한 push와 pop의 짝으로 연결한 것이다. 첫 단계에서는 스택에 $를 push하며, 마지막 단계에서는 $를 스택에서 pop한다. 이에 따라 <math>A_{23}</math>는 두 단계 사이의 계산, 즉 PDA의 <math>q_2</math>에서 <math>q_3</math>까지의 계산을 의미하는 비단말기이다. 즉, <math>A_{14}\rightarrow A_{23}</math> 규칙은 <math>q_1</math>에서 $를 push하는 것으로 시작해 <math>q_4</math>에서 $를 pop하며 끝나는 전체 계산은 <math>q_2</math>에서 <math>q_3</math> 사이에서의 계산과 같다는 것을 의미한다.		을 $에 대한 push와 pop의 짝으로 연결한 것이다. 첫 단계에서는 스택에 $를 push하며, 마지막 단계에서는 $를 스택에서 pop한다. 이에 따라 <math>A_{23}</math>는 두 단계 사이의 계산, 즉 PDA의 <math>q_2</math>에서 <math>q_3</math>까지의 계산을 의미하는 비단말기이다. 즉, <math>A_{14}\rightarrow A_{23}</math> 규칙은 <math>q_1</math>에서 $를 push하는 것으로 시작해 <math>q_4</math>에서 $를 pop하며 끝나는 전체 계산은 <math>q_2</math>에서 <math>q_3</math> 사이에서의 계산과 같다는 것을 의미한다.

			<math>A_{23}\rightarrow 0A_{23}1</math>과 같은 규칙은 아래의 두 전이:
	<math></math>		<math>(q_2,0,\epsilon)\rightarrow (q_2,0)</math>
	<math></math>		<math>(q_3,1,0)\rightarrow (q_3,\epsilon)</math>
	<math></math>		을 0에 대한 push와 pop의 짝으로 연결한 것이다. 또한 <math>A_{23}\rightarrow 0A_{22}1</math>과 같은 규칙은 아래의 두 전이:
	<math></math>		<math>(q_2,0,\epsilon)\rightarrow (q_2,0)</math>
	<math></math>		<math>(q_2,1,0)\rightarrow (q_3,\epsilon)</math>
	<math></math>		을 0에 대한 push와 pop의 짝으로 연결한 것이다. 이때 다른 두 비단말기에 비해 이질적인 <math>A_{22}</math>은 그 정의에 따르면 PDA가 <math>q_2</math>에서 시작해서 다시 <math>q_2</math>로 돌아오는 과정에서 스택의 상태가 처음과 같게 유지되는 모든 문자열들의 집합을 표현하는 비단말기이다. 이에 따라 스택이 유지되기 위해서는 push와 pop의 수가 같아야 하므로, <math>A_{33}</math>에서 유도될 수 있는 문자열은 <math>\epsilon</math> 뿐이다.
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~

	다른 두 비단말기에 비해 이질적인 <math>A_{33}</math>은 <math>~~q_3~~</math>에서 시작해서 다시 <math>~~q_3~~</math>로 돌아오는 ~~계산을~~ 표현하는 비단말기이다. 하지만 <math>A_{33}</math>은 실제로 push 없이 pop만 있는 전이만 존재하기 때문에, 실질적으로 생성에 관여하지 않고, 문법에서는 “중간 기호로만 등장”하는 비단말기이다. 이에 따라 스택이 ~~원상태로 돌아오기~~ 위해서는 push와 pop의 수가 같아야 하므로, <math>A_{33}</math>에서 유도될 수 있는 문자열은 <math>\epsilon</math> 뿐이다.

	~~하지만 <math>q_3</math>에서는 스택에서 pop만 일어나고, push는 전혀 일어나지 않는다.~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~

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

Pinkgo: /* CFG from PDA Example */

2025-10-30T03:49:51Z

CFG from PDA Example

@@ 109번째 줄: / 109번째 줄: @@
   <math>A_{23}\rightarrow 0A_{33}1</math> (0을 push한 후, 0을 pop)
   <math>A_{33}\rightarrow \epsilon</math>
 <math></math>
 <math></math>
 <math></math>
 <math></math>
 <math></math>
 <math></math>
@@ 123번째 줄: / 143번째 줄: @@
 <math></math>
 <math></math>
 ==각주==

Pinkgo: /* CFG from PDA Example */

2025-10-30T02:55:12Z

CFG from PDA Example

← 이전 판		2025년 10월 30일 (목) 02:55 판
103번째 줄:		103번째 줄:

	===CFG from PDA Example===		===CFG from PDA Example===
			[[파일:Figure 3. CFG from PDA Example.png\|섬네일\|250x250픽셀\|Figure 3. CFG from PDA Example]]
			Figure 3에서 CFG는 아래와 같이 유도된다:
			<math>A_{14}\rightarrow A_{23}</math> ($를 push한 후, $를 pop)
			<math>A_{23}\rightarrow 0A_{23}1</math> (0을 push한 후, 0을 pop)
			<math>A_{23}\rightarrow 0A_{33}1</math> (0을 push한 후, 0을 pop)
			<math>A_{33}\rightarrow \epsilon</math>
	<math></math>		<math></math>
	<math></math>		<math></math>
117번째 줄:		123번째 줄:
	<math></math>		<math></math>
	<math></math>		<math></math>
	~~<math></math>~~
	~~<math></math>~~
	~~<math></math>~~

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