4.4.2.1 - Finite-state machines and Mealy output

States, transitions and acceptance

A finite-state machine (FSM) has a finite set of states. Its current state summarises the relevant information from the input received so far. A transition specifies what happens when an input is received in a particular state. In the deterministic examples here, a state and input together determine one next state.

A state diagram draws states as circles and transitions as directed arrows labelled with inputs. An arrow entering a state from nowhere identifies the start state. A double circle identifies an accepting state where one is specified. An accepting state need not be a stopping state: more input may leave it.

Consider a machine that accepts exactly the binary strings containing an even number of 1s. State E means “an even number of 1s received”; O means “an odd number received”. E is the start and accepting state. Receiving 0 does not change the count of 1s, so it leaves either state unchanged. Receiving 1 changes even to odd or odd to even.

[DIAGRAM: asset_slug: fsm-even-ones; description: Two-state recogniser for binary strings with an even number of 1s; E is the start and accepting state]

To trace a string, begin at the start state and consume one input symbol per transition. For 1011 the state sequence is E → O → O → E → O. The final state is O, so the whole string is rejected. For 101, the final state is E and the string is accepted. Decide acceptance after the whole input; visiting E halfway through is insufficient.

The empty string consumes no inputs, so this machine stays in E and accepts it. Zero 1s is an even count. These are acceptance decisions, not emitted output symbols: this recogniser has no transition output.

Converting diagrams and transition tables

A state transition table expresses the same transition rules as a diagram. A no-output table has one row for each current state and one column for each input. Each cell contains the next state. Record the start and accepting states separately; a table of next states alone does not identify them.

The even-1s recogniser has this table:

Start state: E. Accepting state: E.

To convert a diagram to a table, choose a current state, follow its arrow labelled 0 and enter the destination in that cell. Repeat for 1, then for every state. A loop's destination is the state it leaves. Arrow direction matters: the arrow into a state is not necessarily a rule leaving it.

To construct a diagram from a table in your notebook, draw and name every state first. Add the start arrow and any accepting-state double circles. For each cell, draw one arrow from the row's state to the cell's state and label it with the column's input. Use a loop when source and destination are the same. Separate curved arrows can make opposite directions readable. Two inputs leading to the same destination may share an arrow labelled with both inputs, provided the labels clearly mean alternatives.

Check the result systematically: each supplied state/input pair must appear exactly once, destinations must agree, and start/acceptance markings must be retained. Do not silently invent a missing transition. These examples supply a transition for every state and allowed input; an examination task may instead specify a partial machine and explain how missing transitions are treated.

Notebook practice: construct the even-1s diagram from the table without looking at the supplied diagram, then compare every cell with one arrow. This develops the official drawing skill. The marked text questions here assess supported interpretation and table representation rather than claiming to grade your sketch.

Mealy output belongs to a transition

A Mealy machine produces output when it takes a transition. The output depends on both the current state and the current input. Label an arrow input/output, such as 1/0: receiving input 1 produces output 0 and moves along that arrow. The slash separates an input from an output; it does not mean “either symbol”.

Consider a binary sequence detector that emits 1 exactly when the input just received completes the pair 01; otherwise it emits 0. N means “the previous input was not 0, or there is no previous input”; Z means “the previous input was 0”. The start is N.

[DIAGRAM: asset_slug: mealy-detect-01; description: Mealy machine emitting 1 on the transition that completes 01; each arrow is labelled input/output]

From N, a 0 moves to Z but does not yet complete 01, so output is 0. From Z, a 1 completes 01, emits 1 and moves to N. A 0 from Z stays in Z because the most recent input is still 0. Its output is 0. Notice that two transitions entering N have different outputs: N does not have one fixed output.

For input 00101, trace in this order: read the current state and next input; find that transition's output; record the next state. Starting in N gives:

The output string is 00101. No output is emitted merely by entering the start state. For this machine there is one output per input. Acceptance is a separate notion and is not specified for this detector; an output 1 is an event signal, not an accepting-state marker.

For notebook construction, turn each table cell into an arrow labelled input/output and check every pair. Do not put the output inside the state circle: that would suggest output is determined by state alone, which is not the Mealy convention assessed here.