Finite state automata for two regular languages

Question

I have to draw FSAs that accept the following languages over {0,1} and {a, b}

1. (0 | 1)*
2. a* | b*

Now for 1, the language is just any word that consists of 1s and 0s but it also contains the empty word. So, {e, 0, 1, 001, 000, 010, etc}

For 2, the language is words that are all as or all bs but it also contains the empty string. So, {e, a, b, aaaaaa, bbbbbb, ect}

Now my question has to do with what to do when constructing the an FSA for these languages.

Does q0 have to be my accept state since the FSA has to accept the empty word, or can I include the empty word in a transition arrow? Basically, I am just confused about how to get an FSA to accept the empty word while also accepting these other words.

Additionally, for 2, the easiest solution seems to be an FSA with multiple accept states. Is this allowed?

Answer 1

Normally, when we say "FSA", we mean a deterministic FSA, where each transition from one state to another is on exactly one symbol from the input. nondeterministic FSAs sometimes relax these restrictions and allow transitions on empty input. But you should also have seen a proof that such transitions add no power the the NFA, because an NFA with $\epsilon$-transitions can be easily converted to an equivalent one without $\epsilon$-transitions.

Supposing that your FSAs must adhere to this restriction, then yes, since both FSAs must accept the empty string $\epsilon$, each one must have a start state that is an accepting state.

Multiple accepting states are allowed. That is why the definition of an FSA says that there is a set of accepting states, not just a single accepting state.

Answer 2

If a deterministic finite state automaton — and that’s what is normally meant by an FSA — accepts the empty word, its initial state $q_0$ must be an acceptor state. If you look at the definition of a deterministic finite state automaton, you’ll see that the only restriction on the set $A$ of acceptor states is that it be a subset of $Q$, the set of all states. It’s acceptable for all states to be acceptor states, and at the other extreme it’s acceptable for no state to be an acceptor state. Of course in the first case the FSA accepts the language $\Sigma^*$, where $\Sigma$ is the input alphabet, and in the second case it accepts $\varnothing$, the empty language.

The simplest FSA that accepts $(0\mid 1)^*$ has a single state $q_0$, which is an acceptor state, and transitions $q_0\overset{0}\longrightarrow q_0$ and $q_0\overset{1}\longrightarrow q_0$. The simplest FSA that accepts $a^*\mid b^*$ has four states, $q_0,q_a,q_b$, and $q_\infty$, the first three of which are acceptor states, and the following transitions:

$$\begin{array}{lcl} q_0\overset{a}\longrightarrow q_a&\quad&q_0\overset{b}\longrightarrow q_b\\ q_a\overset{a}\longrightarrow q_a&\quad&q_a\overset{b}\longrightarrow q_\infty\\ q_b\overset{a}\longrightarrow q_\infty&\quad&q_b\overset{b}\longrightarrow q_b\\ q_\infty\overset{a}\longrightarrow q_\infty&\quad&q_\infty\overset{a}\longrightarrow q_\infty \end{array}$$