몫 오토마톤

Quotient automaton

컴퓨터 과학, 특히 형식 언어 이론에서, 몫 오토마톤은 그 상태의 일부를 결합함으로써 주어진 비결정론적 유한 오토마톤으로부터 얻을 수 있다.몫은 주어진 오토마톤의 슈퍼셋을 인식한다; 어떤 경우에는 마이힐-네로드 정리에 의해 처리되며, 두 언어는 같다.

형식적 정의

('결정론적') 유한 오토마톤은 A = δ, S, s0, s, δf, S의 5배이다. 여기서, 다음과 같다.

  • δ는 입력 알파벳(공백하지 않은 유한 기호 세트)입니다.
  • S는 유한하고 비어 있지 않은 상태의 집합입니다.
  • s는0 초기상태로 S의 요소이다.
  • θ는 상태 전이 관계이다: θ θ S × δ S
  • S는f 최종 상태의 집합으로,[1][note 1] S의 (아마도 빈) 서브셋입니다.

문자열1 a...ann δ* δ는 i=1, …, n 및n s δf S에 대해i-1 θsi, ai, sθ δ S가1 존재하면 A에 의해 인식된다.A에 의해 인식되는 모든 문자열의 집합을 A에 의해 인식되는 언어라고 하며, L(A)

A 상태의 집합 S에 대한 당량 관계 θ에 대해, 몫 오토마톤 A/=≈ δ, S/,≈ [s0], δ/,≈ Sf/≈θ는 다음과 같이 정의된다[2]: 5 .

  • 입력 알파벳 δ는 A와 동일하며,
  • 상태 집합 S/≈는 S로부터의 모든 동등 상태 클래스의 집합이다.
  • 시작 상태(s0)는 A의 시작 상태의 동등 클래스입니다.
  • 일부 sθ [s] 및 tθ [t]의 경우 θ/([≈s], a, [t])에 의해 정의되는 상태 전이 관계 ≈θ/
  • 최종 상태f 집합 S/≈는 S에서 최종f 상태의 모든 동등성 등급 집합이다.

A/≈를 계산하는 과정은 ≈에 의해 A를 인수분해하는 과정이라고도 합니다.

예

지수 예
오토마톤
도표 		인정된
언어 		의 비율입니까?
A by B by C by
답: Quotient automaton a,b,c,d.gif 1+10+100
B: Quotient automaton a=b,c,d.gif 1*+1*0+1*00 a150b
C: Quotient automaton a=b,c=d.gif 10개** a4b, c4d c450d
D: Quotient automaton a=b=c=d.gif (0+1)* a-b-d cccd a150c

예를 들어 테이블의[note 2] 첫 번째 행에 표시된 자동 A는 다음과 같이 정식으로 정의됩니다.

  • δA = {0,1}.
  • SA = {a,b,c,d}
  • sA
    0     = a,
  • δA = { ⟨a 、 1, b 、 b b , 0 , c 、 c , 0 , d } 。
  • SA
    f     = { b,c,d }.

문자열 {1, 10, 100}의 유한 집합을 인식합니다. 이 집합은 정규 표현 "1+10+100"으로 나타낼 수도 있습니다.

관계())) = { ,a,a', 'a', 'b', 'a', 'b', 'c', 'c', 'c', 'c', 'd', 'd', 'd', 'd', 보다 간략하게 a,cc,d'로 표시되는 관계 = {a,d}의 집합 {a,d}에 대한 등가 되는 관계이다.이 관계에 의해 A의 비율을 구축하면 세 번째 테이블 행에 자동 C가 생성됩니다.이 값은 공식적으로 다음과 같이 정의됩니다.

  • δC = {0,1}.
  • SC = {a,c}[note 3]
  • sC
    0     = a,
  • δC = { ⟨a , 1, a ,, 、 ,a , 0 , c ,, 、 c , 0 , c } 。
  • SC
    f     = { a,c }.

임의의 수의 1로 구성된 모든 문자열의 유한 집합을 인식하며, 그 뒤에 임의의 수의 0이 이어집니다({ ,, 1, 10, 100, 1000, ..., 11, 110, 1100, 11000, ..., 111, ...).}. 이 세트는 정규식** "10"으로도 나타낼 수 있습니다.비공식적으로 상태 a를 상태 b에 접착하고 상태 c를 상태 d에 접착함으로써 A에서 발생하는 것으로 생각할 수 있다.

이 표에는 B = A/a≈b 및 D = C/a≈c와 같은 몇 가지 더 많은 몫 관계가 나와 있습니다.

특성.

  • 모든 오토마톤 A 및 그 상태에서의 모든 등가관계θ에 대해 L(A/)≈은 L(A)[2]: 6 의 슈퍼셋(또는 동일)이다.
  • 일부 알파벳 δ에 대한 유한 오토마톤 A가 주어졌을 때, 만약 δz δz δ δ* : xz δ L(A) ↔ y(A)이면, 당량 관계 δ는 x δ y로 δ* 위에 정의할 수 있다.Myhill-Nerode 정리에 따르면,≈ A/[1]: 65–66 는 A와 같은 언어를 인식하는 결정론적 오토마톤이다.그 결과, also를 개량할 때마다 A의 몫도 A와 같은 언어를 인식한다.

「 」를 참조해 주세요.

메모들

  1. ^ 홉크로프트와 Ullman(section.2.3, 페이지.20)은 S × Ω에서 S의 멱집합에 대한 함수로 δ, viz의 약간 벗어난 정의를 사용한다.
  2. ^ 표의 오토마톤 도표에서는 입력 알파벳과 상태명의 기호가 각각 녹색과 빨간색으로 색칠되어 최종 상태가 이중 원으로 그려진다.
  3. ^ 엄밀하게는 SC = { [a], [b], [c], [d] } = { [a], [c] }입니다.읽기 쉽도록 클래스 괄호는 생략됩니다.

레퍼런스

  1. ^ a b John E. Hopcroft; Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Reading/MA: Addison-Wesley. ISBN 0-201-02988-X.
  2. ^ a b Tristan le Gall and Bertrand Jeannet (Mar 2007). Analysis of Communicating Infinite State Machines Using Lattice Automata (PDF) (Publication Interne). Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) — Campus Universitaire de Beaulieu. ISSN 1166-8687.