## Finite State Machines

An FSM shows the states in which a system can exist, what causes the system to move from one state to another, and what outputs or changes the transition causes.

The system must have a known (finite) number of states.

FSMs can be converted into a circuit, meaning that they can be used to control things such as traffic lights without the need for actual code.

States are connected by transitions (arrows). Transitions should be labelled with the trigger for the transition.

They can be useful for debugging an algorithm or representing it in a way that people who donβt work with code will be able to understand more easily. Start can be indicated with an β coming from nothing.

## Mealy vs Moore Machine

### Mealy Machine

The output is determined by its current state and current inputs.

### Moore Machine

The output is determined solely by the current state.

## State Transition Table

A state transition table shows the current state, the input that is received, the state to move to (next state) and any output produced in the process.

Eg

Current StateInputNext State
Se0Se
Se1So
So0So
Se1Se

### Producing a table

Current StateInputNext State
S0aS1
S1bS2
S2cS1
S1bS2
S2a,bS3
S3--
S0cS0
S0bS3

## State Transition Practice

![[sixth/CompSci/Programming/img/transitionpractice.png]]

Current StateInputNext State
S1IS2
S2PS3
S31|2|3|4S4
S4Numeric DigitS6
S6Numeric DigitS7
S7LetterS9
S9LetterS11
S11--
S1IS2
S2Letter (except P)S13
S13Numeric DigitS16
S16Numeric DigitS17
S17LetterS19
S19LetterS21
S21--
S1Letter (except I)S14
S14Numeric DigitS16
S16LetterS22
S22Numeric DigitS23
S23LetterS19
S19LetterS21
S21Any characterS12
S12Any characterS12
• Not all possible routes are listed in the above table

## Flowchart, Pseudo Code of Finite State Machine?

• Flowcharts are a great way to present information to non-specialists
• Pseudo code is great if your audience are programmers
• Finite State Machines are best suited to control systems

## Natural Languages vs Formal Languages

A natural language is your typical-spoken language - English or Spanish are good examples. They are ambiguous and can be interpreted in multiple ways.

Whereas a formal language is like a formula in maths or science and programming languages. It can only be interpreted in a single way and is very rigid.

### Algorithms

Typically, an algorithm will use a formal language (or will be much closer to formal than natural). A recipe is an example of an algorithm that can be represented using natural languages, with a more formal structure. A recipe can be misinterpreted, a program cannot.

ββ