Автомат Ко-Бючи - Co-Büchi automaton

В теория автоматов, а автомат со-Бючи это вариант Büchi автомат. Единственное отличие - это условие принятия: автомат Ко-Бюхи принимает бесконечное слово. ${\displaystyle w}$ если существует запуск, такой, что все состояния, возникающие бесконечно часто в ходе выполнения, находятся в наборе конечных состояний ${\displaystyle F}$. Напротив, Büchi автомат принимает слово ${\displaystyle w}$ если существует запуск, такой, что по крайней мере одно состояние возникает бесконечно часто в наборе конечных состояний ${\displaystyle F}$.

(Детерминированные) автоматы Ко-Бюхи строго слабее (недетерминированных) автоматов Бюхи.

Формальное определение

Формально детерминированный автомат Ко-Бюхи кортеж ${\displaystyle {\mathcal {A}}=(Q,\Sigma ,\delta ,q_{0},F)}$ который состоит из следующих компонентов:

• ${\displaystyle Q}$ это конечный набор. Элементы ${\displaystyle Q}$ называются состояния из ${\displaystyle {\mathcal {A}}}$.
• ${\displaystyle \Sigma }$ конечное множество, называемое алфавит из ${\displaystyle {\mathcal {A}}}$.
• ${\displaystyle \delta :Q\times \Sigma \rightarrow Q}$ это функция перехода из ${\displaystyle {\mathcal {A}}}$.
• ${\displaystyle q_{0}}$ является элементом ${\displaystyle Q}$, называемое начальным состоянием.
• ${\displaystyle F\subseteq Q}$ это набор окончательного состояния. ${\displaystyle {\mathcal {A}}}$ принимает именно эти слова ${\displaystyle w}$ с бегом ${\displaystyle \rho (w)}$, в котором все бесконечно часто встречающиеся состояния в ${\displaystyle \rho (w)}$ находятся в ${\displaystyle F}$.

В недетерминированный ко-автомат Бюхи, функция перехода ${\displaystyle \delta }$ заменяется соотношением перехода ${\displaystyle \Delta }$. Исходное состояние ${\displaystyle q_{0}}$ заменяется набором начального состояния ${\displaystyle Q_{0}}$. Как правило, термин ко-автомат Бюхи относится к недетерминированному ко-автомату Бюхи.

Для более полного формализма см. Также ω-автомат.

Условия приема

Условие приемки ко-автомата Бюхи формально

${\displaystyle \exists i\forall j:\;j\geq i\quad \rho (w_{j})\in F.}$

Условие приемки Büchi является дополнением условия приемки co-Büchi:

${\displaystyle \forall i\exists j:\;j\geq i\quad \rho (w_{j})\in F.}$

Характеристики

Автоматы Ко-Бюхи замкнуты относительно объединения, пересечения, проекции и детерминизации.