**What is finite state machine?**

The finite state machine also has the following names;

- Finite state automata (FSA)
- Finite automata (FA)
- Finite machines
- Finite state machines

The finite state machine is designed for accepting and rejecting the different strings of the languages from the machine. All regular languages can be represented by the FSA.

The finite state machine has the following parts;

**Start state:**

Representing the start of the machine.

**Final state:**

Representing the successful end of the machine

**Dead/Dummy State:**

Having no meaning in the strings generation. It is only designed to full the requirements of the finite state machines that every state have one transition for each alphabet.

**Transition:**

Representing the reading of the alphabets from the finite state machine.

**Strings:**

Strings are characters are set of characters that can be accepted or rejected by finite state machines.

**What are the rules for building the FSA?**

**1.** Every state has strictly one transition for each alphabet. Suppose there two alphabets in the languages L={a,b}, then each state has strictly had two transitions. One transition for alphabet a and one transition for alphabet b. Let’s have another example, Suppose there three alphabets in the languages L={a,b,c}, then each state has strictly three transitions. One transition for alphabet a, one transition for alphabet b and one transition for alphabet c.

**2.** If the generation of any alphabet from a transition is the cause of generating some strings that are not the part of the language, and it becomes very necessary to put that alphabet on some transition, then generates the alphabet and move the machine to the dead/dummy state. Dummy state means that machine will not generate any string.

**3.** Every string that is part of the language should be accepted by the FSA and every string that is not part of the language should be rejected by the FSA.

**4.** Every language that can be generated by a regular expression can be generated by FSA.

**More examples of Finite State Automata FSA**

- Language of all those string containing aa as a substring
- Language of all those strings starting with a and ending with a
- Language of all those strings starting with a