클린의 알고리즘

이론 컴퓨터 과학, 특히 형식 언어 이론에서 클레네의 알고리즘은 주어진 비결정론적 유한자동화(NFA)를 규칙적인 표현으로 변형시킨다.다른 변환 알고리즘과 함께 정규 언어에 대한 여러 설명 형식의 동등성을 확립한다.같은 방법의 대안 발표로는 브르조조스키와 맥클러스키가 귀속한 「제거법」, 맥노튼과 야마다의 알고리즘,^[1] 아르덴의 보조마 사용 등이 있다.

알고리즘 설명

그로스와 옐런(2004)에 따르면 이 알고리즘은 클레인(1956년)으로 거슬러 올라갈 수 있다.^[2]^[3]결정론적 유한 자동자(DFA)의 경우에 알고리즘의 표시는 Hopcroft와 Ulman(1979)에 제시되어 있다.^[4]아래의 NFA 알고리즘은 Gross와 Yellen(2004)에 이어 발표된다.^[2]

Q = { q,..., Δ_n, q₀, f}인 비계수적 유한 자동측정기 M = (Q₀, Δ, Q, F)가 주어지면 알고리즘은 그 상태를 계산한다.

k보다 높은 숫자의 상태를 거치지 않고 상태 q에서_i q까지_j M을 가져가는 모든 문자열의 R 세트^k
_ij

여기서 "국가를 거치는 것"은 그것을 출입하는 것을 의미하므로 i와 j 둘 다 k보다 높을 수 있지만, 중간 상태는 있을 수 없다.없기 때문에 국가 n보다 높은 번호는 각 세트 Rkij 정규식을 타는 것이고, 그 알고리즘 k을 차근차근 단계)-1,0,...를 계산하 n.은,는 정규식 Rn0j의 시작 상태 q0 qj까지 M을 모든 문자열의 집합을 나타냅니다.accept한 상태의 만약 F){q1,...,qf}집합은 정규식 Rn01...R은ⁿ
_0f M이 받아들인 언어를 나타낸다.

k = -1의 초기 정규식은 i≠j의 경우 다음과 같이 계산된다.

R⁻¹
_ij = a₁ ... q_m_j Δ(q_i,a₁), ..., q_j Δ(q_i,a_m)

그리고 i=j에 대해서는 다음과 같다.

R⁻¹
_ii_i = a₁ ≤ Δ(q_i,a₁), ..., q_i Δ(q_i,a_m)인 where_m

즉, R은⁻¹
_ij i에서 j로의 전환을 나타내는 모든 문자를 언급하고, i=j의 경우에는 also도 포함시킨다.

그 후 각 단계에서 R 식을^k
_ij 이전 식으로부터 계산한다.

R^k
_ij = R^k-1
_ik(R^k-1
_kk)^* R^k-1
_ij R^k-1
_kj

또 다른 방법은 알고리즘의 작동을 이해하기 0n에로 연속적으로 제거된"소거 법",:상태 j> 때 국가 k이 제거되는 상태 i&gt에서 길을 꼬리표를 붙이는 단어를 설명하는 정규식 Rk-1ij, k으로 고려 goi의 가능성을에 대한 k의, Rkij에 다시 써다."엘을 통해 쇼핑을이미미네이트된" 상태 k.

k에 대한 유도를 통해 각 표현 R의^k
_ij 길이가^[5] 기껏해야 길다는 것을 알 수 있다.1/3(4s^k+1+7) - 4) 기호, 여기서 s는 σ의 문자 수를 나타낸다.따라서 M이 받아들인 언어를 나타내는 정규식의 길이는 최대 1/3(4sⁿ⁺¹+7)f - f - 3) 기호로, 여기서 f는 최종 상태의 수를 나타낸다.이러한 지수적 확장은 불가피하다. 왜냐하면 등가 정규식이 지수적 크기여야 하는 DFA의 집단이 존재하기 때문이다.^[6]

실제로 알고리즘을 실행하여 얻은 정규식의 크기는 절차, 즉 0부터 n까지 번호가 매겨지는 순서에 따라 매우 달라질 수 있다.

예

Kleene 알고리즘에 주어진 DFA 예

그림에 표시된 자동화는 M = (Q, Δ, Δ, q₀, F)로 설명할 수 있다.

상태 집합 Q = { q₀, q₁, q₂ q },
입력 알파벳 σ = { a, b },
Δ(q₀,a)=q₀, Δ(q₀,b)=q₁, Δ(q₁,a)=q₂, Δ(q₁,b)=q₁, Δ(q₂,a)=q₁, Δ(q,b)=q, Δ(q,b)=q, Δ(q₂,b)=q₁,
시작 상태 q₀.
허용 상태 집합 F = { q₁ }.

클린의 알고리즘은 초기 정규식을 다음과 같이 계산한다.

R⁻¹ ₀₀	= ε
R⁻¹ ₀₁	= b
R⁻¹ ₀₂	= ∅
R⁻¹ ₁₀	= ∅
R⁻¹ ₁₁	= b ε
R⁻¹ ₁₂	= a
R⁻¹ ₂₀	= ∅
R⁻¹ ₂₁	= a b
R⁻¹ ₂₂	= ε

그 후 R은^k
_ij k^k-1
_ij = 0, 1, 2. R에서 단계별로 계산된다. 클레인 대수 등가치는 정규식을 최대한 단순화하기 위해 사용된다.

0단계

R⁰ ₀₀	= R⁻¹ ₀₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₀ R⁻¹ ₀₀	= (a )	(a ε)^*	(a ε)	ε.	= a^*
R⁰ ₀₁	= R⁻¹ ₀₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₁ R⁻¹ ₀₁	= (a )	(a ε)^*	b	b	= a^* b
R⁰ ₀₂	= R⁻¹ ₀₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₂ R⁻¹ ₀₂	= (a )	(a ε)^*	∅	∅	= ∅
R⁰ ₁₀	= R⁻¹ ₁₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₀ R⁻¹ ₁₀	= ∅	(a ε)^*	(a ε)	∅	= ∅
R⁰ ₁₁	= R⁻¹ ₁₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₁ R⁻¹ ₁₁	= ∅	(a ε)^*	b	b ε	= b ε
R⁰ ₁₂	= R⁻¹ ₁₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₂ R⁻¹ ₁₂	= ∅	(a ε)^*	∅	a	= a
R⁰ ₂₀	= R⁻¹ ₂₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₀ R⁻¹ ₂₀	= ∅	(a ε)^*	(a ε)	∅	= ∅
R⁰ ₂₁	= R⁻¹ ₂₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₁ R⁻¹ ₂₁	= ∅	(a ε)^*	b	a b	= a b
R⁰ ₂₂	= R⁻¹ ₂₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₂ R⁻¹ ₂₂	= ∅	(a ε)^*	∅	ε	= ε

1단계

R¹ ₀₀	= R⁰ ₀₁ (R⁰ ₁₁)^* R⁰ ₁₀ R⁰ ₀₀	= a^*b	(b ε)^*	∅	a^*	= a^*
R¹ ₀₁	= R⁰ ₀₁ (R⁰ ₁₁)^* R⁰ ₁₁ R⁰ ₀₁	= a^*b	(b ε)^*	(b ε)	a^* b	= b^^ b b
R¹ ₀₂	= R⁰ ₀₁ (R⁰ ₁₁)^* R⁰ ₁₂ R⁰ ₀₂	= a^*b	(b ε)^*	a	∅	= bba^^
R¹ ₁₀	= R⁰ ₁₁ (R⁰ ₁₁)^* R⁰ ₁₀ R⁰ ₁₀	= (b ε)	(b ε)^*	∅	∅	= ∅
R¹ ₁₁	= R⁰ ₁₁ (R⁰ ₁₁)^* R⁰ ₁₁ R⁰ ₁₁	= (b ε)	(b ε)^*	(b ε)	b ε	= b^*
R¹ ₁₂	= R⁰ ₁₁ (R⁰ ₁₁)^* R⁰ ₁₂ R⁰ ₁₂	= (b ε)	(b ε)^*	a	a	= b^* a
R¹ ₂₀	= R⁰ ₂₁ (R⁰ ₁₁)^* R⁰ ₁₀ R⁰ ₂₀	= (a b)	(b ε)^*	∅	∅	= ∅
R¹ ₂₁	= R⁰ ₂₁ (R⁰ ₁₁)^* R⁰ ₁₁ R⁰ ₂₁	= (a b)	(b ε)^*	(b ε)	a b	= (a b) b^*
R¹ ₂₂	= R⁰ ₂₁ (R⁰ ₁₁)^* R⁰ ₁₂ R⁰ ₂₂	= (a b)	(b ε)^*	a	ε	= (a b) b a^* ε

2단계

R² ₀₀	= R¹ ₀₂ (R¹ ₂₂)^* R¹ ₂₀ R¹ ₀₀	= 아바^^	((a b)ba^* ε)^*	∅	a^*	= a^*
R² ₀₁	= R¹ ₀₂ (R¹ ₂₂)^* R¹ ₂₁ R¹ ₀₁	= 아바^^	((a b)ba^* ε)^*	(a b)b^*	a^* b^* b	= a^* b (a b) b)^*
R² ₀₂	= R¹ ₀₂ (R¹ ₂₂)^* R¹ ₂₂ R¹ ₀₂	= 아바^^	((a b)ba^* ε)^*	((a b)ba^* ε)	a^* b^* ba	= a^^ b (a b)^* a^*
R² ₁₀	= R¹ ₁₂ (R¹ ₂₂)^* R¹ ₂₀ R¹ ₁₀	= b^* a	((a b)ba^* ε)^*	∅	∅	= ∅
R² ₁₁	= R¹ ₁₂ (R¹ ₂₂)^* R¹ ₂₁ R¹ ₁₁	= b^* a	((a b)ba^* ε)^*	(a b)b^*	b^*	= (a (b) b)^*
R² ₁₂	= R¹ ₁₂ (R¹ ₂₂)^* R¹ ₂₂ R¹ ₁₂	= b^* a	((a b)ba^* ε)^*	((a b)ba^* ε)	b^* a	= (a (b) b)^* a
R² ₂₀	= R¹ ₂₂ (R¹ ₂₂)^* R¹ ₂₀ R¹ ₂₀	= ((a b)ba^* ε)	((a b)ba^* ε)^*	∅	∅	= ∅
R² ₂₁	= R¹ ₂₂ (R¹ ₂₂)^* R¹ ₂₁ R¹ ₂₁	= ((a b)ba^* ε)	((a b)ba^* ε)^*	(a b)b^*	(a b) b^*	= (a b) (a b) b)^*
R² ₂₂	= R¹ ₂₂ (R¹ ₂₂)^* R¹ ₂₂ R¹ ₂₂	= ((a b)ba^* ε)	((a b)ba^* ε)^*	((a b)ba^* ε)	(a b) b a^* ε	= ((a b) b^* a)^*

q는₀ 시작 상태이고 q는₁ 유일한 허용 상태기 때문에 정규식²
₀₁ R은 자동화가 허용하는 모든 문자열의 집합을 의미한다.

참고 항목

Floyd-Warshall 알고리즘 — 특정 Kleene 대수학을 사용하여 Kleene 알고리즘에 의해 구현될 수 있는 가중 그래프에 대한 알고리즘
항성 높이 문제 — 주어진 DFA에 해당하는 모든 정규 표현식의 최소 항성 중 내포 깊이는 얼마인가?
일반화된 항성 높이 문제 — 정규식에서 추가적으로 보완 연산자가 허용될 경우, 클린의 알고리즘 출력에 대한 항성의 내포 깊이가 고정된 바운드로 제한될 수 있는가?
Thompson의 구조 알고리즘 — 정규식을 유한 자동식으로 변환

참조

^ McNaughton, R.; Yamada, H. (March 1960). "Regular Expressions and State Graphs for Automata". IRE Transactions on Electronic Computers. EC-9 (1): 39–47. doi:10.1109/TEC.1960.5221603. ISSN 0367-9950.
^ ^a ^b Jonathan L. Gross and Jay Yellen, ed. (2004). Handbook of Graph Theory. Discrete Mathematics and it Applications. CRC Press. ISBN 1-58488-090-2. 여기: 제2.1장, 페이지 65에 R13을 언급한다.
^ Kleene, Stephen C. (1956). "Representation of Events in Nerve Nets and Finite Automate" (PDF). Automata Studies, Annals of Math. Studies. Princeton Univ. Press. 34. 여기: 제9장, 페이지 37-40
^ John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. 여기: 섹션 3.2.1 페이지 91-96
^ 보다 정확히 말하면, "a", "a_i", ", ",^* ", ", ", ","; 괄호를 세지 않는 규칙적인 표현 기호 수입니다.
^ 그루버, 헤르만, 홀저, 마르쿠스(2008년).아세토, 루카, Damgård, 이반. 골드버그, 레슬리 앤, Halldórsson, Magnús M.;Ingólfsdóttir, 안나, Walukiewicz, 이고리(eds.)."유한 자동자, Digraph 연결, 레귤러 표현 크기".자동자, 언어와 프로그래밍.강의 노트 컴퓨터 과학으로.스프링거 베를린 하이델베르크. 5126:39–50. doi:10.1007/978-3-540-70583-3_4.아이 에스비엔 9783540705833.S2CID 10975422..정리 16.

[1] McNaughton, R.; Yamada, H. (March 1960). "Regular Expressions and State Graphs for Automata". IRE Transactions on Electronic Computers. EC-9 (1): 39–47. doi:10.1109/TEC.1960.5221603. ISSN 0367-9950.

[gross2004handbook-2] Jonathan L. Gross and Jay Yellen, ed. (2004). Handbook of Graph Theory. Discrete Mathematics and it Applications. CRC Press. ISBN 1-58488-090-2. 여기: 제2.1장, 페이지 65에 R13을 언급한다.

[3] Kleene, Stephen C. (1956). "Representation of Events in Nerve Nets and Finite Automate" (PDF). Automata Studies, Annals of Math. Studies. Princeton Univ. Press. 34. 여기: 제9장, 페이지 37-40

[4] John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. 여기: 섹션 3.2.1 페이지 91-96

[5] 보다 정확히 말하면, "a", "a_i", ", ",^* ", ", ", ","; 괄호를 세지 않는 규칙적인 표현 기호 수입니다.

[6] 그루버, 헤르만, 홀저, 마르쿠스(2008년).아세토, 루카, Damgård, 이반. 골드버그, 레슬리 앤, Halldórsson, Magnús M.;Ingólfsdóttir, 안나, Walukiewicz, 이고리(eds.)."유한 자동자, Digraph 연결, 레귤러 표현 크기".자동자, 언어와 프로그래밍.강의 노트 컴퓨터 과학으로.스프링거 베를린 하이델베르크. 5126:39–50. doi:10.1007/978-3-540-70583-3_4.아이 에스비엔 9783540705833.S2CID 10975422..정리 16.

[1]

[2]

[3]

[4]

[5]

[6]

Search

클린의 알고리즘

네임스페이스

더

목차

알고리즘 설명

예

참고 항목

참조