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?
$\begingroup$
$\endgroup$
2
-
$\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$– vznCommented Sep 20, 2012 at 18:52
-
$\begingroup$ This seems to be a homework assignment to be. What have you tried? $\endgroup$– RaphaelCommented Sep 23, 2012 at 14:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Sep 23, 2012 at 21:47