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 오토마타는 결합, 교차, 투영 및 결정화에 따라 폐쇄됩니다.