Examples of a finite automaton
Published in
2 min readMar 26, 2022
Idea
Example
- The circles are the states of the automaton. The one with an arrow coming from nowhere or labeled start is called the initial state or the beginning of the computation.
- The labels or “numbers” on the arrows are called transitions and the labels are the alphabet dictating what to do next
- The arrow labeled “1” or transition “1” from A to B tells us that if we are at state A and we read “1” or one, we go to state B. On the other hand, if we are at A and we read zero or “0”, we go the state C
- Double circled states are called accepting states. If the computation ends at any of the accepting states, the machine outputs accept, otherwise it outputs reject.
Example
Example
Backward computation
- Choose and accept state E
- Incoming transitions to E
- Input ends with 0
- Penultimate states: B, D
- Incoming transitions to B, D
- Input ends with 10
