Co-Büchi automaton
ऑटोमेटा सिद्धांत में, एक सह-बुची ऑटोमेटन बुची ऑटोमेटन का एक प्रकार है। एकमात्र अंतर स्वीकार करने की शर्त हैः एक को-बुची ऑटोमेटन एक अनंत शब्द को स्वीकार करता है यदि कोई दौड़ मौजूद है, जैसे कि दौड़ में असीम रूप से अक्सर होने वाली सभी अवस्थाएं अंतिम स्थिति सेट में होती हैं। इसके विपरीत, एक बुची ऑटोमेटन एक शब्द को स्वीकार करता है यदि कोई रन मौजूद है, जैसे कि कम से कम एक अवस्था अनंत रूप से अक्सर अंतिम अवस्था सेट में होती है। (नियतात्मक) को-बुची ऑटोमेटा (गैर-नियतात्मक) बुची ऑटोमेटा की तुलना में सख्ती से कमजोर हैं। औपचारिक परिभाषा औपचारिक रूप से, एक नियतात्मक सह-बुची स्वचालित एक टुपल है जिसमें निम्नलिखित घटक होते हैंः एक परिमित समूह है। के तत्वों को अवस्थाएँ कहा जाता है। एक परिमित समुच्चय है जिसे वर्णमाला कहा जाता है। का संक्रमण कार्य है। एक तत्व है, जिसे प्रारंभिक अवस्था कहा जाता है। अंतिम राज्य सेट है। दौड़ के साथ ठीक उन शब्दों को स्वीकार करता है, जिसमें सभी असीम रूप से अक्सर होने वाली अवस्थाएँ होती हैं। एक गैर-निर्धारक सह-बुची स्वचालित में, संक्रमण कार्य को एक संक्रमण संबंध के साथ प्रतिस्थापित किया जाता है। प्रारंभिक अवस्था को प्रारंभिक अवस्था समुच्चय से बदल दिया जाता है। आम तौर पर, सह-बुची ऑटोमेटन शब्द गैर-निर्धारक सह-बुची ऑटोमेटन को संदर्भित करता है। अधिक व्यापक औपचारिकता के लिए ω-ऑटोमेटन भी देखें। स्वीकृति की शर्त एक सह-बुची स्वचालित की स्वीकृति की शर्त औपचारिक रूप से है बुची स्वीकृति की शर्त सह-बुची स्वीकृति शर्त का पूरक हैः गुण को-बुची स्वचालित संघ, प्रतिच्छेदन, प्रक्षेपण और निर्धारण के तहत बंद हैं। परिमित स्वचालित