Co-Büchi 오토마톤

Co-Büchi automaton

오토마타 이론에서, 공동 뷔치 오토마톤뷔치 오토마톤의 변형이다.유일한 차이점은 허용 조건입니다. Co-Büchi 오토마톤은 실행 중에 무한히 자주 발생하는 모든 상태가 최종 상태 F(\ F에 포함되도록 무한 w(\ w 받아들입니다. 반면 Büchi 오토마톤은 w(\ w 있는 경우 w(\ w를 받아들입니다.최소 1개의 상태가 최종 상태 F F에서 무한히 자주 발생하도록 실행을 시작합니다.

(결정론) Co-Büchi 오토마타는 (결정론적이지 않은) Büchi 오토마타보다 엄격히 약하다.

형식적 정의

공식적으로는 결정론적 co-Büchi 오토마톤은 다음과 같은 성분으로 구성된 (Q , ,,F ) { style \ {A} = ( Q , \ , \ sigma , \ , _ { , F } 입니다.

  • Q 유한 집합입니다.라고 불립니다
  • \Sigma )는 A의 알파벳으로 불리는 유한 집합입니다.
  • \ Q는A{A의 변환 함수입니다.
  • 0 QQ로 초기 상태라고 불립니다.
  • Q ( \ F \ 최종 상태 세트입니다. {(는 ( w )\ 에서 무한히 자주 발생하는 모든 상태가F {\ F인 단어 w를 정확하게 .

비결정론적 Co-Büchi 오토마톤에서는 전이함수(\ 전이관계(\로 대체되고 초기상태 0})가 초기상태 로 대체된다.일반적으로 Co-chi 용어.비결정론적 공동 Büchi 오토마톤에 귀속됩니다.

보다 포괄적인 형식주의에 대해서는, 「자동화」도 참조해 주세요.

수용 조건

co-Büchi automaton의 수용 조건은 공식적으로 다음과 같다.

Büchi 수용 조건은 공동 Büchi 수용 조건을 보완하는 것이다.

특성.

Co-Büchi 오토마타는 결합, 교차, 투영 및 결정화에 따라 폐쇄됩니다.