Regular Expressions - 편집 역사

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

2026-01-15T15:23:55Z

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

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

Pinkgo: /* Regular Algebra */

2025-10-08T21:20:55Z

Regular Algebra

← 이전 판		2025년 10월 8일 (수) 21:20 판
87번째 줄:		87번째 줄:
	이들이 참인 것은 언어의 정의를 사용하여 증명할 수 있다. 예를 들어, <math>R \circ \epsilon = R</math>은:		이들이 참인 것은 언어의 정의를 사용하여 증명할 수 있다. 예를 들어, <math>R \circ \epsilon = R</math>은:
	<math>L(R\circ \epsilon = R) = L(R) \circ L(\epsilon)</math>		<math>L(R\circ \epsilon = R) = L(R) \circ L(\epsilon)</math>
	<math> = \{xy\|x\in L(R),\,\,y\in L(\epsilon)\}</math>		<math> = \{xy \| x\in L(R),\,\,y\in L(\epsilon)\}</math>
	<math> = \{x\epsilon \| x \in L(R)\} = \{x\|x\in L(R)\} = L(R)</math>		<math> = \{x\epsilon \| x \in L(R)\} = \{x\|x\in L(R)\} = L(R)</math>
	과 같이 증명된다.		과 같이 증명된다.

	==Derivatives of RE==		==Derivatives of RE==

Pinkgo: /* Derivatives of RE */

2025-10-07T02:53:41Z

Derivatives of RE

← 이전 판		2025년 10월 7일 (화) 02:53 판
95번째 줄:		95번째 줄:
	언어 <math>L \subseteq \Sigma*</math>, 문자 <math>a \in \Sigma</math>가 정의되었을 때,		언어 <math>L \subseteq \Sigma*</math>, 문자 <math>a \in \Sigma</math>가 정의되었을 때,
	Brzozowski derivative: <math>a^{-1}L=\{x\|ax \in L\}</math>		Brzozowski derivative: <math>a^{-1}L=\{x\|ax \in L\}</math>
	즉, 언어 L에 속하는 문자열 중, 앞에 a가 붙은 것에서 a를 떼어낸 나머지 부분 집합을 의미한다. 예를 들어 <math>L = \{</math>"<math>ab</math>"<math>, </math>"<math>ac</math>"<math>, </math>"<math>aac</math>"<math>, </math>"<math>bc</math>"<math>\}</math>를 <math>a</math>에 대한 미분을 취하면, <math>a^{-1}L = \{</math>"<math>b</math>"<math>,</math>"<math>c</math>"<math>,</math>"<math>ac</math>"<math>\}</math>이다. 이때 <math>L \subseteq \Sigma*</math>이 정규 언어이고 <math>a \in \Sigma</math>이면 <math>a^{-1}L</math>도 정규 언어이다.		즉, 언어 L에 속하는 문자열 중, 앞에 a가 붙은 것에서 a를 떼어낸 나머지 부분 집합을 의미한다. 예를 들어 <math>L = \{</math>"<math>ab</math>"<math>, </math>"<math>ac</math>"<math>, </math>"<math>aac</math>"<math>, </math>"<math>bc</math>"<math>, </math>"<math>bac</math>"<math>\}</math>를 <math>a</math>에 대한 미분을 취하면, <math>a^{-1}L = \{</math>"<math>b</math>"<math>,</math>"<math>c</math>"<math>,</math>"<math>ac</math>"<math>\}</math>이다. 이때 <math>L \subseteq \Sigma*</math>이 정규 언어이고 <math>a \in \Sigma</math>이면 <math>a^{-1}L</math>도 정규 언어이다.

	이때 정규 표현식 R을 문자 a로 미분한 것을 <math>\partial_aR</math>이라 정의한다. 이때 해당 정의는 재귀적으로 주어진다. 아래는 정규 표현식의 미분 정의이다:		이때 정규 표현식 R을 문자 a로 미분한 것을 <math>\partial_aR</math>이라 정의한다. 이때 해당 정의는 재귀적으로 주어진다. 아래는 정규 표현식의 미분 정의이다:

Pinkgo: /* Obtaining a DFA from a Regular Expression */

2025-10-07T02:35:58Z

Obtaining a DFA from a Regular Expression

← 이전 판		2025년 10월 7일 (화) 02:35 판
141번째 줄:		141번째 줄:

	===Obtaining a DFA from a Regular Expression===		===Obtaining a DFA from a Regular Expression===
	[[파일:Figure 8. RE to DFA ~~example 1~~.png\|섬네일\|Figure 8. RE to DFA ~~example~~ 1]]		[[파일:Figure 8. RE to DFA .png\|섬네일\|Figure 8. RE to DFA 1]]
	~~[[파일:Figure 9. RE to DFA example 2.png\|섬네일\|Figure 9. RE to DFA example 2~~]]
	Brzozowski 미분을 사용하면 어떤 정규표현식이 나타내는 DFA를 직접적으로 구성할 수 있다. 이는 아래의 절차를 가진다:		Brzozowski 미분을 사용하면 어떤 정규표현식이 나타내는 DFA를 직접적으로 구성할 수 있다. 이는 아래의 절차를 가진다:
	# 상태 집합 <math>Q</math>를 정규표현식 자체만을 포함하는 <math>\{R\}</math>로 시작한다.		# 상태 집합 <math>Q</math>를 정규표현식 자체만을 포함하는 <math>\{R\}</math>로 시작한다.
	# 아직 탐색되지 않은 표현식 <math>E \in Q</math>에 대해, 각 문자 <math>a \in \Sigma</math>로 미분 <math>\partial_aE</math>를 계산한다.		# [[파일:Figure 8. RE to DFA 2.png\|섬네일\|Figure 8. RE to DFA 2]]아직 탐색되지 않은 표현식 <math>E \in Q</math>에 대해, 각 문자 <math>a \in \Sigma</math>로 미분 <math>\partial_aE</math>를 계산한다.
	#* 새로운 표현식이 기존 것과 동치(congruent)하지 않다면 <math>Q</math>에 추가한다.		#* 새로운 표현식이 기존 것과 동치(congruent)하지 않다면 <math>Q</math>에 추가한다.
	#* 해당 과정은 Brzozowski 정리에 의해 유한 단계에서 종료된다.		#* 해당 과정은 Brzozowski 정리에 의해 유한 단계에서 종료된다.

Pinkgo: /* Obtaining a DFA from a Regular Expression */

2025-10-02T04:28:40Z

Obtaining a DFA from a Regular Expression

← 이전 판		2025년 10월 2일 (목) 04:28 판
141번째 줄:		141번째 줄:

	===Obtaining a DFA from a Regular Expression===		===Obtaining a DFA from a Regular Expression===
			[[파일:Figure 8. RE to DFA example 1.png\|섬네일\|Figure 8. RE to DFA example 1]]
			[[파일:Figure 9. RE to DFA example 2.png\|섬네일\|Figure 9. RE to DFA example 2]]
	Brzozowski 미분을 사용하면 어떤 정규표현식이 나타내는 DFA를 직접적으로 구성할 수 있다. 이는 아래의 절차를 가진다:		Brzozowski 미분을 사용하면 어떤 정규표현식이 나타내는 DFA를 직접적으로 구성할 수 있다. 이는 아래의 절차를 가진다:
	# 상태 집합 <math>Q</math>를 정규표현식 자체만을 포함하는 <math>\{R\}</math>로 시작한다.		# 상태 집합 <math>Q</math>를 정규표현식 자체만을 포함하는 <math>\{R\}</math>로 시작한다.
149번째 줄:		151번째 줄:
	# Accept states: <math>\epsilon \in L(E)</math>를 만족하는 표현식 <math>E \in Q</math>를 accept 상태로 둔다.		# Accept states: <math>\epsilon \in L(E)</math>를 만족하는 표현식 <math>E \in Q</math>를 accept 상태로 둔다.
	# 전이 함수 <math>\delta</math>: <math>\delta(E, a) = E_a</math>. 이때 <math>E_a = \partial_aE \in Q</math>		# 전이 함수 <math>\delta</math>: <math>\delta(E, a) = E_a</math>. 이때 <math>E_a = \partial_aE \in Q</math>
	이를 통해서 DFA <math>= (Q,\Sigma,\delta, q_0,F)</math>가 완전히 정의된다. 이를 적용한 예시는		이를 통해서 DFA <math>= (Q,\Sigma,\delta, q_0,F)</math>가 완전히 정의된다. 이를 적용한 예시는 figure 8, 9과 같다:

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

Pinkgo: /* Derivatives of RE */

2025-10-02T04:26:17Z

Derivatives of RE

@@ 95번째 줄: / 95번째 줄: @@
   언어 <math>L \subseteq \Sigma*</math>, 문자 <math>a \in \Sigma</math>가 정의되었을 때,
   Brzozowski derivative: <math>a^{-1}L=\{x|ax \in L\}</math>
 즉, 언어 L에 속하는 문자열 중, 앞에 a가 붙은 것에서 a를 떼어낸 나머지 부분 집합을 의미한다. 예를 들어 <math>L = \{</math>"<math>ab</math>"<math>, </math>"<math>ac</math>"<math>, </math>"<math>aac</math>"<math>, </math>"<math>bc</math>"<math>\}</math>를 <math>a</math>에 대한 미분을 취하면, <math>a^{-1}L = \{</math>"<math>b</math>"<math>,</math>"<math>c</math>"<math>,</math>"<math>ac</math>"<math>\}</math>이다. 이때 <math>L \subseteq \Sigma*</math>이 정규 언어이고 <math>a \in \Sigma</math>이면 <math>a^{-1}L</math>도 정규 언어이다.
 <math></math>
-<math></math>
+이때 정규 표현식 R을 문자 a로 미분한 것을 <math>\partial_aR</math>이라 정의한다. 이때 해당 정의는 재귀적으로 주어진다. 아래는 정규 표현식의 미분 정의이다:
-<math></math>
+# <math>\partial_ab =
-<math></math>
+\begin{cases}
-<math></math>
+\epsilon, & if\,\,a=b \\
-<math></math>
+\empty, & otherwise
-<math></math>
+\end{cases}
-<math></math>
+</math> <math>\rightarrow</math> a와 같은 문자면 지워지고 ε, 다르면 공집합
-<math></math>
+# <math>\partial_a\epsilon = \empty</math> <math>\rightarrow</math> 빈문자열은 시작 문자가 없으므로 매칭 불가
-<math></math>
+# <math>\partial_a\empty = \empty</math> <math>\rightarrow</math> 공집합은 당연히 미분해도 공집합
-<math></math>
+# <math>\partial_a(R_1\cup R_2) = \partial_aR_1 \cup \partial_aR_2</math> <math>\rightarrow</math> 합은 각각 미분 후 합치므로 분배법칙 적용
-<math></math>
+# <math>\partial_a(R_1R_2) =
-<math></math>
+\begin{cases}
 ==각주==

Pinkgo: /* Regular Algebra */

2025-10-02T03:17:41Z

Regular Algebra

← 이전 판		2025년 10월 2일 (목) 03:17 판
84번째 줄:		84번째 줄:
	* 항등원(Identity): <math>R \circ \epsilon = R = \epsilon \circ R</math>		* 항등원(Identity): <math>R \circ \epsilon = R = \epsilon \circ R</math>
	* 영원소(Zero): <math>R \circ \empty = \empty = \empty \circ R</math>		* 영원소(Zero): <math>R \circ \empty = \empty = \empty \circ R</math>
	* Kleene star 확장: <math>R* = \epsilon \cup (R \circ R)~~</math>~~ = \epsilon \cup (R \circ R)<ref>star 연산을 재귀적으로 정의하는 것을 의미한다.</ref>		* Kleene star 확장: <math>R* = \epsilon \cup (R \circ R) = \epsilon \cup (R \circ R)</math><ref>star 연산을 재귀적으로 정의하는 것을 의미한다.</ref>
	<math></math>		이들이 참인 것은 언어의 정의를 사용하여 증명할 수 있다. 예를 들어, <math>R \circ \epsilon = R</math>은:
	<math></math>		<math>L(R\circ \epsilon = R) = L(R) \circ L(\epsilon)</math>
	<math></math>		<math> = \{xy\|x\in L(R),\,\,y\in L(\epsilon)\}</math>
	<math></math>		<math> = \{x\epsilon \| x \in L(R)\} = \{x\|x\in L(R)\} = L(R)</math>
	<math></math>		과 같이 증명된다.
	<math></math>
	<math></math>		==Derivatives of RE==
	<math></math>		정규표현식의 미분(derivative)는 아래와 같이 정의된다:
	<math></math>		언어 <math>L \subseteq \Sigma*</math>, 문자 <math>a \in \Sigma</math>가 정의되었을 때,
	<math></math>		Brzozowski derivative: <math>a^{-1}L=\{x\|ax \in L\}</math>
	<math></math>		즉, 언어 L에 속하는 문자열 중, 앞에 a가 붙은 것에서 a를 떼어낸 나머지 부분 집합을 의미한다. 예를 들어 <math>L = \{</math>"<math>ab</math>"<math>, </math>"<math>ac</math>"<math>, </math>"<math>aac</math>"<math>, </math>"<math>bc</math>"<math>\}</math>를 <math>a</math>에 대한 미분을 취하면, <math>a^{-1}L = \{</math>"<math>b</math>"<math>,</math>"<math>c</math>"<math>,</math>"<math>ac</math>"<math>\}</math>이다. 이때 <math>L \subseteq \Sigma*</math>이 정규 언어이고 <math>a \in \Sigma</math>이면 <math>a^{-1}L</math>도 정규 언어이다.
	<math></math>
	<math></math>
	<math></math>
	<math></math>		<math></math>
	<math></math>		<math></math>

Pinkgo: /* Converting GNFA to RE */

2025-10-02T02:49:27Z

Converting GNFA to RE

@@ 72번째 줄: / 72번째 줄: @@
 Figure 5, 6, 7은 주어진 GNFA에서 정규표현식을 도출하는 예시이다.
 <math></math>
 <math></math>

Pinkgo: /* Converting GNFA to RE */

2025-09-29T16:07:38Z

Converting GNFA to RE

← 이전 판		2025년 9월 29일 (월) 16:07 판
70번째 줄:		70번째 줄:
	[[파일:Figure 4. path through q rip.png\|가운데\|섬네일\|Figure 4. path through <math>q_rip</math>]]		[[파일:Figure 4. path through q rip.png\|가운데\|섬네일\|Figure 4. path through <math>q_rip</math>]]
	<math>q_{rip}</math>을 거쳐서 가는 경우는 figure 4와 같이 표현된다. 따라서 이와 같은 경우에서 읽어들이는 문자열은 <math>R_1(R_2)R_3</math>이다. 따라서 두 경로를 합친 전이 라벨은 <math>\delta'(q_i, q_j) = R_1(R_2)R_3 \cup R_4</math>이다.		<math>q_{rip}</math>을 거쳐서 가는 경우는 figure 4와 같이 표현된다. 따라서 이와 같은 경우에서 읽어들이는 문자열은 <math>R_1(R_2)R_3</math>이다. 따라서 두 경로를 합친 전이 라벨은 <math>\delta'(q_i, q_j) = R_1(R_2)R_3 \cup R_4</math>이다.

			Figure 5, 6, 7은 주어진 GNFA에서 정규표현식을 도출하는 예시이다.
	<math></math>		<math></math>
	<math></math>		<math></math>
77번째 줄:		79번째 줄:
	<math></math>		<math></math>
	<math></math>		<math></math>



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

Pinkgo: /* Constructing a RE from a NFA */

2025-09-29T16:06:01Z

Constructing a RE from a NFA

← 이전 판		2025년 9월 29일 (월) 16:06 판
58번째 줄:		58번째 줄:

	===Converting GNFA to RE===		===Converting GNFA to RE===
	GNFA에서 RE를 얻는 절차는 기저 조건과, 재귀적 단계로 나뉜다. 먼저 기저 조건은 ~~아래와 같다:~~		[[파일:Figure 5. GNFA example.png\|섬네일\|250x250픽셀\|Figure 5. GNFA example]]
	* 만약 상태가 2개(시작/종료)뿐이면, 답은 <math>\delta(q_{start}, q_{accept})</math>이다.		GNFA에서 RE를 얻는 절차는 기저 조건과, 재귀적 단계로 나뉜다. 먼저 기저 조건은 만약 상태가 2개(시작/종료)뿐이면, 답은 <math>\delta(q_{start}, q_{accept})</math>이라는 것이다. 이는 시작 상태에서 종료 상태로 전이하는 라벨이 곧 정규표현식이라는 것을 의미한다. 재귀적 단계는 아래와 같다:
	이는 시작 상태에서 종료 상태로 전이하는 라벨이 곧 정규표현식이라는 것을 의미한다. 재귀적 단계는 아래와 같다:		# [[파일:Figure 6. Remove Q2.png\|섬네일\|250x250픽셀\|Figure 6. Remove Q2]][[파일:Figure 7. Remove Q1.png\|섬네일\|250x250픽셀\|Figure 7. Remove Q1]]상태가 2개 초과라면, 제거할 상태 <math>q_{rip}</math>을 하나 선택한다. 이때 <math>q_{start}, q_{end}</math>는 제외한다.
	# 상태가 2개 초과라면, 제거할 상태 <math>q_{rip}</math>을 하나 선택한다. 이때 <math>q_{start}, q_{end}</math>는 제외한다.
	# <math>q_{rip}</math>를 제외한 새로운 상태 집합 <math>Q' = Q - \{q_{rip}\}</math>을 정의한다.		# <math>q_{rip}</math>를 제외한 새로운 상태 집합 <math>Q' = Q - \{q_{rip}\}</math>을 정의한다.
	# 이에 따라 전이 <math>\delta</math>를 <math>\delta'(q_i, q_j) = R_1(R_2)*R_3 \cup R_4</math>와 같이 재정의한다. 이때 <math>R_1,R_2,R_3,R_4</math>는 아래와 같다:		# 이에 따라 전이 <math>\delta</math>를 <math>\delta'(q_i, q_j) = R_1(R_2)*R_3 \cup R_4</math>와 같이 재정의한다. 이때 <math>R_1,R_2,R_3,R_4</math>는 아래와 같다:
68번째 줄:		67번째 줄:
	## <math>R_3 = \delta(q_{rip}, q_j)</math>		## <math>R_3 = \delta(q_{rip}, q_j)</math>
	## <math>R_4 = \delta(q_i, q_j)</math>		## <math>R_4 = \delta(q_i, q_j)</math>
			<math>q_i</math>에서 <math>q_j</math>로 가는 경우는 <math>q_{rip}</math>를 거치는 경우와 아닌 경우 두 가지로 나뉜다. 먼저, <math>R_4 = \delta(q_i, q_j)</math>는 <math>q_i</math>에서 <math>q_j</math>로 <math>q_{rip}</math>을 거치지 않고 전이가 이뤄지는 라벨을 의미한다.<br>
	[[파일:Figure 4. path through q rip.png\|가운데\|섬네일\|Figure 4. path through <math>q_rip</math>]]		[[파일:Figure 4. path through q rip.png\|가운데\|섬네일\|Figure 4. path through <math>q_rip</math>]]
	<math>q_i</math>에서 <math>q_j</math>로 가는 경우는 <math>q_{rip}</math>를 거치는 경우와 아닌 경우 두 가지로 나뉜다. 먼저, <math>R_4 = \delta(q_i, q_j)</math>는 <math>q_i</math>에서 <math>q_j</math>로 <math>q_{rip}</math>을 거치지 않고 전이가 이뤄지는 라벨을 의미한다.<br>
	<math>q_{rip}</math>을 거쳐서 가는 경우는 figure 4와 같이 표현된다. 따라서 이와 같은 경우에서 읽어들이는 문자열은 <math>R_1(R_2)R_3</math>이다. 따라서 두 경로를 합친 전이 라벨은 <math>\delta'(q_i, q_j) = R_1(R_2)R_3 \cup R_4</math>이다.		<math>q_{rip}</math>을 거쳐서 가는 경우는 figure 4와 같이 표현된다. 따라서 이와 같은 경우에서 읽어들이는 문자열은 <math>R_1(R_2)R_3</math>이다. 따라서 두 경로를 합친 전이 라벨은 <math>\delta'(q_i, q_j) = R_1(R_2)R_3 \cup R_4</math>이다.
	<math></math>		<math></math>
78번째 줄:		77번째 줄:
	<math></math>		<math></math>
	<math></math>		<math></math>



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