Finite State Machine

Introduction

Finite State Machines are one of the most elementary topics in the Theory of Computation. Here in this blog, we are going to take a detailed look at finite state machines as well as their types. Before going deep into the finite state machine. First, let's explore the state machine model.

Also Read, Moore Machine

What is the state machine model?

• This is a reactive or event-driven model
• Or embedded system whose processing behavior is dependent on state transition
• It is represented as “states, Events, Actions, and Transitions”
• State: It is a representation of the current situation
• Event: It is a representation of input to the state
• Action: It is a representation of an activity to be performed by the state machine
• Transition: It is movement from one state to another

Also See, Simplification of CFG

 What is the Finite State machine model?

• It is one with a heaving number of states finite.
• A finite state machine is a machine that is used to recognize patterns.
• The input to a finite automata machine is a string of symbols, and the state of the machine is changed correspondingly. When the desired symbol is found in the input, the transition occurs.
• The Automata can either migrate to the next state or stay in the current state while transitioning.
• FA can be in one of two states: accept or reject. The automata will accept when the input string has been correctly digested, and the automata have reached its final state.
• The finite automata or finite state machine is an abstract machine with five elements or tuples. It has some predefined set of rules for moving from one state to another, but it also has a dependency on the applied input symbol. 
•  It's essentially an abstract representation of a digital computer.

Also read - Arden's theorem

Example: Embedded system for driver seat belt warning in automotive here we can decide the states are alarm off, waiting, alarm on and events are ignition key on, ignition key off, waiting time expires and seat belt on using FMS

A finite automaton consists of the following:

                 Q: a finite set of states
                 ∑: a finite set of input symbol
                 q0: initial state
                 F: final state
                 δ: Transition function 
                  Representation of machine
                  { Q, Σ, q, F, δ }

1. We can define the transition function as:

 δ: Q x ∑ →Q  

Finite state machine or finite automata can be further characterized into two ways:

Also see, Turing Machine in TOC.

Deterministic Finite Automata (DFA)

In DFA, the state to which the machine will move can be determined for each input symbol. As a result, it's known as a Deterministic Automaton. The machine is known as a Deterministic Finite Machine or Deterministic Finite Automaton because it has a finite number of states.

DFA consists of 5 tuples {Q, Σ, q, F, δ}. 

Q: a set of all states.

Σ: a set of input symbols. ( Symbols which machine takes as input )

q: Initial state. ( Starting state of a machine )

F: a set of the final state.

δ: Transition Function, defined as δ: Q X Σ --> Q.

In a DFA, the machine only goes to one state for each input character. Every state for each input symbol has a transition function defined. DFA doesn't accept the null move, which means the DFA cannot change the state without any input character. One thing to keep in mind is that a pattern can have several DFAs. A DFA with the fewest possible states is generally preferred.

Example:

L1  =  Set of all strings that start with ‘0’

      =  {0,00,01,000,010,011,000,............}