아르덴의 법칙

Arden's rule

이론 컴퓨터 과학에서 아르덴의 보조정리라고도 알려진 아르덴의 법칙은 언어 방정식의 어떤 형태에 대한 수학적인 진술이다.

배경

(공식) 언어는 단순히 문자열 집합이다. 그러한 집합은 어떤 언어 방정식을 통해 지정될 수 있으며, 이는 결국 언어에 대한 연산을 기반으로 한다. 언어 방정식은 숫자 방정식을 닮은 수학적 문장이지만, 변수는 숫자보다는 형식 언어의 값을 가정한다. A와 B 두 언어에서 가장 흔한 작업으로는 조합 A와 결합 A ∪B가 있다. 마지막으로, 단일 피연산자를 취하는 작업으로서, 세트 A는* 언어 A의 클레인 별을 가리킨다.

아르덴의 통치 성명

Arden의 법칙에 따르면, X = A∪X set B에서 X에 대한 해결책인 세트* AbB가 가장 작은 언어라고 한다. 여기서 X, A, B는 문자열의 집합이다. 더구나 A 집합에 빈말이 들어 있지 않으면 이 해법은 독특하다.[1][2]

동등하게, 세트 B⋅A는* X = X⋅A ∪ B의 X에 대한 해법인 가장 작은 언어다.

적용

Arden의 규칙은 Kleene의 알고리즘에서와 같이 일부 유한한 오토마톤을 정규식으로 변환하는 것을 돕는 데 사용될 수 있다.

참고 항목

메모들

  1. ^ Daintith, John (2004). "Arden's Rule". Archived from the original on 13 February 2010. Retrieved 10 March 2010.
  2. ^ Sutner, Klaus. "Algebra of Regular Languages" (PDF). Archived from the original (PDF) on 2011-07-08. Retrieved 15 Feb 2011.

참조

  • 아든, D. N. (1960년) 지연된 논리와 유한한 상태 기계, 1페이지 35, 미국 미시건 주 앤아버 미시간 대학 출판부
  • Dean N. Arden (Oct 1961). "Delayed Logic and Finite State Machines". Proc. 2nd Ann. Symp. on Switching Circuit Theory and Logical Design (SWCT), Detroit/MI. (개방 액세스 추상)
  • 존 E. 홉크로프트와 제프리 D. Ulman, Automata 이론 소개, 언어 및 계산, Addison-Wesley 출판, Reading Massachusetts, 1979. ISBN 0-201-02988-X. 제2장: 유한 자동식 및 정규식, 페이지 54.
  • Arden, D.N. 유한 상태 기계 이론 소개, 모노그래프 12호, 이산 시스템 개념 프로젝트, 1965년 6월 28일.