0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Usually, deterministic FSAs do not have transitions on the empty word. Typically the definition only allows them to make a transition on a single input symbol: the transition function $\delta$ is defined as a function $\Sigma\times Q\to Q$ where $\Sigma$ is the input alphabet and $Q$ is the set of states. $\endgroup$ – MJD Oct 10 '13 at 17:42
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If you have a good intuition for computer programs, it sometimes helps to imagine a simple computer program for performing the same task, and then construct the FSA in an analogous way. $\endgroup$ – MJD Oct 10 '13 at 19:49
0
$\begingroup$

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}$$

$\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.