Finite Automaton States and Transitions Explained

What a finite automaton is

A finite automaton is a simple machine that reads a string of symbols one by one. It has a small set of conditions called states. At any moment the machine is in exactly one state. An input symbol tells the machine which arrow, also called a transition, to follow. The arrow points from the current state to the next state. When the last symbol is read, the machine either accepts the string or rejects it depending on whether it ends in an accepting state.

How the parts fit together

1. Define the alphabet – the list of symbols the machine may see, for example 0 and 1 for binary strings. 2. List the states – give each state a name, such as A, B, C. 3. Mark a start state – the state where reading begins. 4. Mark accepting states – usually drawn with a double circle; reaching one at the end means acceptance. 5. Draw arrows – for each state and each possible input, draw an arrow to the state the machine should move to. The arrow is labelled with the input symbol that triggers it.

Worked example: strings that end in 01

Consider the set of binary strings that finish with the pattern 01. We build a deterministic automaton with three states:

• State A is the start state. It means "no relevant pattern seen yet".
• State B means "the last symbol read was 0".
• State C is an accepting state meaning "the last two symbols read were 01". The alphabet is {0,1}. The arrows are:
• From A, reading 0 moves to B; reading 1 stays in A.
• From B, reading 0 stays in B (another 0 does not complete the pattern); reading 1 moves to C.
• From C, reading 0 moves back to B (the pattern 01 is broken but a new 0 could start a new occurrence); reading 1 returns to A. If we feed the machine the string 11001, the walk is: A –(1)→ A –(1)→ A –(0)→ B –(0)→ B –(1)→ C. The final state is C, an accepting state, so the string is accepted. The same walk can be described without any code: each step follows the arrow labelled by the next digit.

Reading a diagram correctly

When you look at a diagram, first locate the start circle. Follow the arrow whose label matches the first input symbol. Continue until the input is exhausted. If you ever reach a state with no arrow for the current symbol, the machine is undefined for that string and the string is rejected. At the end, check whether the circle you are in is drawn with a double outline – that tells you if the string belongs to the language.

Mistakes beginners often make

• Forgetting the start state – without a clear starting point the walk cannot begin.
• Leaving some input symbols without arrows – every state must have an outgoing arrow for each symbol in the alphabet; otherwise the machine is incomplete.
• Confusing accepting and non-accepting circles – the double circle is the only visual cue that a state signals acceptance.
• Treating arrows as optional – an arrow is mandatory for the current input; the machine never “stays” unless the arrow explicitly loops back to the same state.
• Mixing up deterministic and nondeterministic ideas – in a deterministic automaton there is exactly one arrow for each state-symbol pair. Adding two arrows with the same label creates a nondeterministic machine, which changes how acceptance is decided.

Where this idea appears in textbooks

The textbook example of a DFA that recognises binary strings ending in 01 is used to illustrate how regular languages are built. Another classic example is a machine that accepts strings with an even number of 0s; it has two states, one for "even" and one for "odd". Both examples show how the simple combination of states, inputs and arrows can capture patterns that appear in programming language lexical analysis and in simple text-search utilities.

Check yourself

1. Question: In a DFA with states X and Y, alphabet {a,b}, start state X, and accepting state Y, an arrow from X to Y is labelled a and an arrow from Y to X is labelled b. Does the string "aba" get accepted? Answer: Yes. Walk: X –a→ Y –b→ X –a→ Y, ending in Y which is accepting.
2. Question: What mistake is made if a state has no arrow for the symbol "0"? Answer: The automaton is incomplete; the string containing that symbol would be rejected because the transition is undefined.
3. Question: How many arrows must a deterministic automaton with 4 states and an alphabet of size 2 have at minimum? Answer: Eight arrows – each of the 4 states needs one arrow for each of the 2 symbols.

For more details on this topic see the Automa course.