If you take a course in programming languages, you will also learn about finite state machines. Usually, you will call it a DFA (deterministic finite automata).

While finite state machines with outputs are essentially DFAs, the purpose behind them is different.

Formally, the definition of a DFA is:

- Q, a set of states
- S, an single state which is an element of Q. This is the start state.
- F, a set of states designated as the final states
- Sigma, the input alphabet
- delta, a transition function that maps a state and a letter from the input alphabet, to a state

DFAs are used to recognize a language, L. A language is a set of strings made from characters in the input alphabet. If a language can be recognized by a DFA, it is said to have a regular grammar.

To use a DFA, you start in an initial state, and process the input string a character at a time. For example, if the input alphabet consists of "a" and "b", then a typical question is to ask whether the string "aaab" is accepted by a DFA.

To find out whether it is accepted, you start off in the state state, S. Then you process each character (first "a", then "a", then "a", and finally "b"). This may cause you to move from one state to another. After the last character is processed, if you are in a final state, then the string is in the language. Otherwise, it's not in the language.

There are some languages that can't be recognized by a DFA (for example, palindromes). Thus, a DFA, while reasonably powerful, there are other (mathematical) machines that are more powerful.

Often, tokens in programming languages can be described using a regular grammar.

- Q, a set of states
- S, an single state which is an element of Q. This is the start state.
- Sigma, the input alphabet
- Pi, the output alphabet
- delta, a transition function that maps a state and a letter from the input alphabet, to a state and a letter from the output alphabet.

The primary difference is that there is no set of final states, and that the transition function not only puts you in a new state, but also generates an output symbol.

The goal of this kind of FSM is not accepting or rejecting strings,
but generating a set of outputs given a set of inputs. Recall that
a black box takes in inputs, processes, and generates outputs.
FSMs are one way of describing how the inputs are being processed,
based on the inputs *and* state, to generate outputs. Thus,
we're very interested in what output is generated.

In DFAs, we don't care what output is generated. We care only whether a string has been accepted by the DFA or not.

Since we're talking about circuits, the input alphabet is going
to be the set of **k** bit bitstrings, while the output alphabet
is the set of **m** bit bitstrings.

We'll look at this more informally, just in case you're confused.

Each of the circle is a state. For now, all you need to know is that, at any given moment, you are in one state. Think of this as a game, where there are circles drawn on the ground, and at any moment, you are standing in exactly one circle.

Each of the circle is given a unique binary number. The number
of bits used depends on the total number of states. If there are N
states, then you need **ceil( lg N )** bits (the ceiling of log base
2 of N). The states are labelled with the letter q, plus subscripts.
In this example, it's **q _{1}q_{0}**.

You may have **k** input bits. The input bits tell you which
state to transition to. For example, if you have 2 input bits
(**x _{1}x_{0}**), then there are four possible out
going edges (

Thus, the number of edges depends on the number of bits used in the input.

State | 00 (Start) | 01 | 10 | 01 | 01 | 10 |

Input | 1 | 1 | 0 | 0 | 1 |

So, you may start in state 00, reading input 1 (see column 1 of the table), which puts you in state 01. At that point, you read in input 1 (see column 2), and go into state 10 (column 3), etc.

We modify the FSM shown above, by adding outputs. Moore machines
add outputs to each state. Thus, each state is associated with an output.
When you transition into the state, the output corresponding to the
state is produced. The information in the state is typically written
as 01/1. 01 indicates the state, while 1 indicates the output.
01/1 is short hand for **q _{1}q_{0} = 01/z = 1**

The number of bits in the output is arbitary, and depends on whatever your application needs. Thus, the number of bits may be less than, equal, or greater than the number of bits used to represent the state.

Let's look at an example of a Moore machine.

In this example, you see two bits for the state and two bits for
the output. Thus, when you see 00/01 inside one of the circles,
it is shorthand for **q _{1}q_{0} = 00 / z_{1}
z_{0} = 01**.

The timing diagram isn't too hard to follow. Basically, you
will start off in some state (let's say, 00), and draw the diagram
to indicate what happens to the state (**q _{1}q_{0}**)
and to the output (

You'll notice the input does NOT change at the positive edge.
That way, it's easier for you to tell the value of the input
at the positive edge. To make it easier to read, I've added
the value of **x** at the positive edge. Thus, the inputs are
1, 1, 0, 1, 1, 0.

Let's look at the timing diagram at the first positive edge (drawn
with a vertical line). Before the first edge, the state,
**q _{1}q_{0}** = 00. The input is 1. This
should put us in state 01 (i.e.,

You have to read down the columns. The first column says that
the machine is in state 00, with output 01. The second column says
that the machine is in state 01, with output 11. The reason the
second column says that is due to the input, **x**, read in
at the first positive edge. The input **x** is 1, which caused
the FSM to move from state 00 to state 01.

The value of the state and output are placed in the middle, but the really, it's the dark line that tells you when this happens. The state and output changes value on the positive edge (technically, it takes a small, but finite amount of time after the positive edge for the state and output to finally settle down, but we'll draw the diagrams as if it happens instantaneously---even though it doesn't).

Here's the rest of the timing diagram.

A Mealy machine has outputs that are a function of state
and input, that is
That is, z = f( **q _{k-1}**,...,

We usually indicate that the output is depedent on current state and input by drawing the output on the edge. In the example below, look at the edge from state 00 to state 01. This edge has the value 1/1. This means, that if you are in state 00, and you see an input of 1, then you output a 1, and transition to state 01.

Thus, 1/1 is short hand for **x = 1 / z = 1**.

Here's a sample Mealy machine.

One thing you will notice is the numbering of the states. Usually, if there are 3 states, we number them 00, 01, and 10, since those are the first 3 UB numbers. However, given that we're using two bits, we can, in principle, pick any 3 of the 4 possible 2-bit numbers.

One reason we might want to pick something else besides 00, 01, and 10 is because implementing an FSM with minimal gates often involves picking the correct state numbering. Thus, if you're careful which state is numbered, say, 00, 01, and 11, you may be able to create a circuit that has fewer gates.

However, minimization of the circuit based on well-chosen state
numberings is outside the scope of the course. We only pick the
state numberings just to make a note that this *could* happen,
but we won't take advantage of this fact.

Another interesting point to observe is how a Mealy machine differs from a Moore. Already we said that a Mealy machine's output may depend on both the values of state and input variables. We can see this in the example. Look at the edge from 00 to 01.

This edge says that if a 1 is input, we will transition to state 01 and output a 1. Now look at the loop in state 01. This says that if the input is 1, we will loop back to state 01, and output a 0.

So, in the first case, going to state 01 outputs a 1, whereas in the second case, going to state 01 outputs a 0. In a Moore machine, this would not happen. The output depends only on the state you transition into, not how you got into that state.

The following timing diagram shows what happens to the state
(**q _{1}q_{0}**) and to the output (

Just to see what happens. Initially, we're in state 00, with an output of 0. It doesn't terribly matter what the initial output is. Unlike the Moore machine, a Mealy machine's output doesn't depend on the current state.

In state 00, we see an input of a 1. This takes us to state 01, with an output of 1. If you read the second column of numbers, you see 0 and a 1 (which is state 01), followed by a 1 (which is the output).

Initially, you might think not. A Mealy machine can have its output depend on both input and state. Thus, if we ignore the state, we should be able to convert a Moore machine to a Mealy machine.

It's not so easy to see that you can convert an arbitrary Mealy machine to a Moore machine.

It turns out that the two machines are equivalent. What does that mean? It means that given a Moore machine, you can create a Mealy machine, such that if both machines are fed the same sequence of inputs, they will both produce the same sequence of outputs. You can also convert from a Mealy machine to its equivalent Moore machine, and again generate the same outputs given the same sequence of inputs.

Actually, to be precise we must ignore one fact about Moore machines. Moore machines generate output even if no input has been read in. So, if you ignore this initial output of the Moore machine, you can convert between one machine and the other.

The actual algorithm is beyond the scope of the course. However,
the basic idea of converting a Mealy machine to a Moore machine is
to increase the number of states. Roughly speaking, if you have
a Mealy machine with N states, and there are **k** bits of input,
you may need up to **2 ^{k}**N states in the equivalent
Moore machine.

Effectively, the new states record information about how that state was reached.

CPUs use finite state machines as control units to sychronize the fetch, execute, decode cycle. These machines can be rather sophisticated, however, programs exists to convert the finite state machine into actual flip flops and logic gates.