image/svg+xml
A machine is made of nodes connected by labelled arrows
The arrows are labelled with letters from an alphabet
The machine is used to test a string of letters from that alphabetcalled the input string
The machine begins at the node labelled "start"
Follow the arrow labelled with the first letter of the input stringThis takes us to a second node
From the second node, follow the arrow labelled with the second letter...and so on, until the entire input string is used
If the machine finishes in a square state, it accepts the input stringIf it finishes in a round state, it rejects the input
START
a
b
a
Example Machine with alphabet {a, b}
Example Input String: "ab"
The input string is accepted.This machine accepts "b" and "ab"It rejects all other strings
b
a, b
a, b
START
a
b
a
b
a, b
a, b
START
a
b
a
b
a, b
a, b
START
a
b
a
b
a, b
a, b