2
$\begingroup$

Consider a Büchi automaton $\mathcal{A}$ with the modified acceptance condition, that an $\omega$-word $\mathcal{w}$ is accepted by $\mathcal{A}$ iff every run $\rho$ of $\mathcal{A}$ on $\mathcal{w}$ is accepting (rather than at least one run being accepting). I need to show that this automaton also accepts only $\omega$-regular languages. How do I go about doing that?

$\endgroup$
  • $\begingroup$ ?! thats a pretty good CS program over there in india if they get into Buchi automata as sophomore undergraduates... does that happen much in the US or elsewhere? hint, think you need to use the defn of Buchi automata =) $\endgroup$ – vzn Sep 20 '12 at 18:52
  • $\begingroup$ This seems to be a homework assignment to be. What have you tried? $\endgroup$ – Raphael Sep 23 '12 at 14:17
2
$\begingroup$

Let $S$ and $F$ be the set of all states and all accepting states of $\mathcal{A}$, respectively. For $t \in S \setminus F$, let $\mathcal{A}$ be the automaton obtained by making $t$ the only accepting state. For $t \in S \setminus F$, let $\mathcal{B}_t$ be the automaton obtained by removing all states in $F$, and making $t$ the starting state. We think of $\mathcal{A}_t$ as an NFA, and of $\mathcal{B}_t$ as a Büchi automaton. The following language is $\omega$-regular: $$ L = \overline{\sum_{t \in S \setminus F} L(\mathcal{A}_t) L(\mathcal{B}_t)}. $$ An $\omega$-word $w$ is not in $L$ if and only if on some run of $\mathcal{A}$, no accepting state appears infinitely often. Therefore an $\omega$-word $w$ is in $L$ if and only if on all runs of $\mathcal{A}$, some accepting state appears infinitely often.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.