Finite-state machine.

Question

I have a problem with the transition function of a finite-state machine. I understand that can be represented by transition table or state diagram but unfortunately in some exercises I do not understand how to make the two things.

For example, the exercise proposed by the professor in class, asks to make the finite-state machine that recognizes the language of strings on the alphabet $\{a, b\}$ in which the penultimate character is a b.

Unfortunately I can not go on. Could you help me, please?

Thank you very much

Answer 1

Clearly we must have an initial state; call it $s_0$. Can it be an acceptor state? No, because the empty word is not in the language, so we need at least one other state.

The states of a finite state automaton are used to keep track of important information. In the case of the language $L$ consisting of all words over $\{a,b\}$ whose penultimate letter is $b$, the only important information is whether we’ve just read a $b$ or not: if we’ve just read a $b$, the next input, whether it’s $a$ or $b$, must take the machine to an acceptor state. On the other hand, if we’ve just read an $a$, the next input must not take us to an acceptor state, or we could accept words like $aa$ or $ab$ that aren’t in $L$. Thus, we need a state $s_b$ that tells us that we’ve just read a $b$: the only way to get to that state is to read a $b$. After that reading either an $a$ or a $b$ should take us to an acceptor state, so that if the input stops after that next input, the machine will accept the word. And since it always matters whether we’ve just read a $b$ or not, reading an $a$ should take us to a different state from reading a $b$; call this state $s_a$.

Suppose that we’ve just read a $b$, and we now read an $a$, so that we’re in state $s_a$. This should be in an acceptor state, in case the input stops there, but if there’s any more input, it’s as if we were starting over: if this $ba$ is followed by an $a$, it’s as if we’d started at the beginning with a first character $a$, and if this $ba$ is followed by a $b$, it’s as if we’d begun with a first character $b$. Thus, the transitions out of $s_a$ should exactly mimic those out of $s_0$, and a first attempt at a transition table might look like this:

$$\begin{array}{c|c|c} \text{State}&\text{Input }a&\text{Input }b&\text{Acceptor?}\\ \hline s_0&s_0&s_b&\text{no}\\ s_b&s_a&s_b&?\\ s_a&s_0&s_b&\text{yes} \end{array}$$

The problem comes when we try to decide whether $s_b$ should be an acceptor state. If we say yes, the machine will accept the word $b$, which is not in $L$. On the other hand, if we say no, it won’t accept $bb$, which is in $L$. Neither possibility actually works. The problem is that one state isn’t enough to distinguish two significantly different situations:

• we’ve just read a $b$ that was preceded by another $b$, so we should be in an acceptor state, and the next state that we visit must also be an acceptor state; and
• we’ve just read a $b$ that was not preceded by another $b$, so we shouldn’t be in an acceptor state, though the next state that we visit must be an acceptor state.

What this means is that our one state $s_b$ that tells us that we’ve just read a $b$ isn’t enough: we need to split it into two states: one, which I’ll call $s_{bb}$, that we enter when we’ve just read a $b$ that was immediately preceded by another $b$, and another, which I’ll call $s_b$, that we enter when we read a $b$ that was not immediately preceded by another $b$. State $s_{bb}$ must be an acceptor state, and state $s_b$ must not.

Our four states then convey the following information:

• $s_{bb}$: We’ve just read a $b$, and the input before that was also a $b$.
• $s_b$: We’ve just read a $b$, and the previous input, if any, was an $a$.
• $s_a$: We’ve just read an $a$, and the previous input was a $b$.
• $s_0$: Either there has been no input, or we’ve just read an $a$, and the previous input, if any, was also an $a$.

Here’s a transition table that summarizes what I’ve said so far about this automaton:

$$\begin{array}{c|c|c} \text{State}&\text{Input }a&\text{Input }b&\text{Acceptor?}\\ \hline s_0&s_0&s_b&\text{no}\\ s_a&s_0&s_b&\text{yes}\\ s_b&s_a&?&\text{no}\\ s_{bb}&?&?&\text{yes} \end{array}$$

Can you fill in the three blanks to make an automaton that recognizes the language $L$?

Answer 2

I suspect you haven't been introduced to the concept of non-determinism, where from a state $p$ on input $c$ you can make transitions to more than one state. Think of such a machine as not making a choice between which move to make, but rather making all possible transitions (perhaps in alternate universes, if you'd like to imagine it that way). A nondeterministic automaton accepts an input string if it reaches a final state in at least one of the universes. The addition of nondeterminism can make automaton design much simpler. Here's a nondeterministic automaton for your "penultimate $\mathtt{b}$" language, where I've shaded the final state: