A Muller automaton is defined as a tuple $\text{M} = (\text{Q}, \text{I}, \Sigma, \rightarrow, \text{T})$ where:
- $\text{Q}$ is a finite set of states;
- $\text{I} \subseteq \text{Q}$ is the set of initial states;
- $\Sigma$ is the finite alphabet;
- $\rightarrow \subseteq \text{Q} \times \Sigma \times \text{Q}$ is the transition relation; and
- $T \subseteq 2^{\text{Q}}$ is the accept table.
A run of $\text{M}$ on a word $x = a_{1} \dots a_{n}$ is a sequence of the form $\rho = q_{0} a_{1} q_{1}\dots q_{n – 1} a_{n} q_{n}$ where $ q_{0} \in \text{I}$ and $q_{i– 1} \overset{a_{i}}{\rightarrow} q_{i}$ for each $i \leq n$. For a run $\rho$ as above, we define $vs(\rho) =\left \{ q_{0},\dots,q_{n}\right \}$, the set of visited states along the run $\rho$. We say that $\text{M}$ accepts a word $x$ if there is a run $\rho$ of $\text{M}$ on $x$ such that $vs(\rho) \in \text{T}$. The language accepted by $\text{M}$, denoted $\text{L(M)}$, is the set $\left \{ x \in \Sigma ^{\ast} \mid x \text{ is accepted by M} \right \}$.
Consider the Muller automaton whose states and transitions are depicted below. The initial state is $\left \{ q_{0} \right \}$.
-
Consider the run $\rho_{1} = q_{0}a q_{a}a q_{a}b q_{b}$ on the word $aab$. What is $vs(\rho_{1})?$ Now, Consider the run $\rho_{2} = q_{0} b q_{b} b q_{b}$ on the word $bb$. What is $vs(\rho_{2})?$
-
What is the language accepted by the above automaton when the accept table is $\left \{ \left \{ q_{0}, q_{a}, q_{b} \right \} \right \}?$
-
What should the accept table be in order to accept $a^{\ast}?$
