# Finite Automata | Discrete Mathematics

In this article, we will learn about the **introduction of finite automata, some components of finite machine and types of finite automata**.

Submitted by Prerana Jain, on August 28, 2018

## Finite state machine

A finite state machine (FSM) is similar to a finite state automation (FSA) except that the finite state machine **"prints"** an output using an output alphabet distinct from the input alphabet. The final definition is as follow:

**A finite state machine (also called complete sequential machine ) M( A, S, Z, S0, f, g) consists of six points.**

- A finite set
**A**of input alphabet. - A finite set
**S**of internal state. - A finite set
**z**of output symbol. - An initial state
**S0**in**S**. - A next-state function
**f**from**S X A**into**S**. - An output function
**g**from**S X A**into**Z**.

## Components of finite state machine

**Input type**

The input type is divided into a square and each square contains a single symbol from the input alphabet **X**. The end squares of the tape contain end markers at the left end and **$** at the right end. The absence of end markers in the input tape indicates that there is an infinite length of the tape. The left to right sequence of symbol between the end markers is the input string to be processed.

**Reading head**

The head examines only one square at a time and can move on square either to the left or to the right. For further analysis are restrict the movement of **R** head only to the right side.

**Finite control**

The input to the finite control will be usually symboled under the **R-head** say a or the present state of the machine say **q** to give the following output:

- A motion of
**R**head along the tape to the next square. - The next state of the finite state machine given by
**& (q, a)**.

**Transition system**

The finite labeled graph in which a state is represented by the vertex or node and the directed edges indicates the transition of a state and the edges are labeled with input/output is known as transition graph or a transition system.

In the normal transition diagram, the initial state is represented by a circle with an arrow pointing towards it, the final state by two concentric circles and the other states are represented by just a circle.

### Types of finite Automata

There are two types of finite automata:

**1) Deterministic finite automata**

Some moves of the machine can be uniquely determined by the input symbol and present state. The DFA can be defined with 5 tuples **(Q, X, &, q0, F)**. When,

**Q**- is a finite non-empty set of states.**X**- is a finite non-empty set of input called input alphabet.**&**- is a function which maps**Q x X**into**q**and is usually called direct transition function. This is the function which describes the change of states driving the transition. This mapping is usually represented by a transition table or a transition diagram.**Qo E Q**- is the initial state and,**F C Q**- is the set of final states. It is assumed here that there may be more than one final state.

**2) Non- deterministic finite Automata**

Some moves of the machine can not uniquely determine by the input symbol and present state. The NDFA can be defined with 5 tuples. (Q, X, f, q0, F). Where,

**Q**- is a finite non-empty set of states.**X**- is a finite non-empty set of inputs.**&**- is the transition function mapping from**Q x X**into**2Q**which is the power set of**Q**, the set of all subset of**Q**.**q0 E Q**- is the initial state.**F C Q**- is the set of final states.

The difference between the deterministic and non- deterministic automata is only in **&**. For deterministic automation, the outcome is a state i.e. an element of **Q** for non- deterministic automation the outcome is a subset of **Q**.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions