# Computing - Finite State Machines

> Source: https://ollybritton.com/notes/a-level/computing/topics/finite-state-machines/ · Updated: 2021-01-05 · Tags: computing, school, safe-to-post-online, regular-languages

##### ![PHOTO STATE](state.png) What does this symbol represent in FSM??
A state.

##### ![PHOTO START STATE](start-state.png) What does this symbol represent in FSM??
The start state.

##### ![PHOTO END OR ACCEPT STATE](end-or-accept-state.png) What does this symbol represnt in FSM??
The end or accept state.

##### ![PHOTO TRANSITION](transition.png) What does this symbol represent in FSM??
A transition.

##### What does the language recognised by a FSM consist of??
All string accepted by the finite state machine.

##### What is a finite state machine??
An abstract model of computation that is used to model logic.

##### What is an end or an accepting state??
A state which is reached when a valid string is entered.

##### What inputs do finite state machines accept??
A string.

##### In relation to FSM, what are strings made out of??
Symbols from a defined alphabet.

##### Do finite state machines need an end or accepting state??
No.

##### What would the two states for a FSM machine be for a light turning on and off at the push of a button??
* Light on
* Light off

##### When in the "light on" state of a FSM machine for a light turning on and off at the push of a button, what are the two transitions you can make??
* Button pressed
* Button not pressed

##### What is a finite state machine with output called??
A Mealy Machine.

##### How are transitions labelled on a mealy machine??
$$
\text{input}/\text{output}
$$

##### What is the difference between a finite state machine and a mealy machine??
They generate an output on a state transition.

### 2021-01-06
##### What are the 4 columns for a Mealy Machine's state transition table??
* Input
* Current state
* Output
* Next state

##### What is a state transition table??
A table showing what happens to each input at each state.

##### ![PHOTO STATE TRANSITION DIAGRAM](state-transition-diagram.png) Explain in words the above part of a state sequence table??
A $0$ is inputed while at state $S1$. This causes an output of $1$ and the machine moves to state $S0$.

##### What is a common use of a Mealy Machine??
To recognise substrings.

##### ![PHOTO SUBSTRING MEALY MACHINE](substring-mealy-machine.png) What substring does this Mealy Machine recognise??
$$
10
$$

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt