# Finite Automaton

An automaton with a finite number of states is called a **Finite Automaton** (FA) or **Finite State Machine** (FSM).

Contents

### Formal definition of a Finite Automaton

An automaton can be represented by a 5-tuple (Q, ∑, δ, q_{0}, F), where −

**Q**is a finite set of states.**∑**is a finite set of symbols, called the**alphabet**of the automaton.**δ**is the transition function.**q**is the initial state from where any input is processed (q_{0}_{0}∈ Q).**F**is a set of final state/states of Q (F ⊆ Q).

### Alphabet

**Definition**− An**alphabet**is any finite set of symbols.**Example**− ∑ = {a, b, c, d} is an**alphabet set**where ‘a’, ‘b’, ‘c’, and ‘d’ are**alphabets**.

### String

**Definition**− A**string**is a finite sequence of symbols taken from ∑.**Example**− ‘cabcad’ is a valid string on the alphabet set ∑ = {a, b, c,d}

### Length of a String

**Definition**− It is the number of symbols present in a string. (Denoted by**|S|**).**Examples**−- If S=‘cabcad’, |S|= 6
- If |S|= 0, it is called an
**empty string**(Denoted by**λ**or**ε**)

### Kleene Star

**Definition**− The set**∑**is the infinite set of all possible strings of all possible lengths over^{*}**∑**including**λ**.**Representation**− ∑^{*}= ∑_{0}∪ ∑_{1}∪ ∑_{2}∪…….**Example**− If ∑ = {a, b}, ∑^{*}= {λ, a, b, aa, ab, ba, bb,………..}

### Kleene Closure/Plus

**Definition**− The set**∑**is the infinite set of all possible strings of all possible lengths over^{+}**∑**excluding**λ**.**Representation**− ∑^{+}= ∑_{0}∪ ∑_{1}∪ ∑_{2}∪…….∑

^{+}= ∑^{*}− { λ }**Example**− If ∑ = { a, b } , ∑^{+}={ a, b, aa, ab, ba, bb,………..}

### Language

**Definition**− A language is a subset of ∑^{*}for some alphabet ∑. It can be finite or infinite.**Example**− If the language takes all possible strings of length 2 over ∑ = {a, b}, then L = { ab, bb, ba, bb}

## Construction of an FA from an RE

We can use Thompson’s Construction to find out a Finite Automaton from a Regular Expression. We will reduce the regular expression into smallest regular expressions and converting these to NFA and finally to DFA.

Some basic RA expressions are the following −

** Case 1** − For a regular expression ‘a’, we can construct the following FA −

** Case 2** − For a regular expression ‘ab’, we can construct the following FA −

** Case 3** − For a regular expression (a+b), we can construct the following FA −

** Case 4** − For a regular expression (a+b)*, we can construct the following FA −

### Method

Step 1 |
Construct an NFA with Null moves from the given regular expression. |

Step 2 |
Remove Null transition from the NFA and convert it into its equivalent DFA. |

### Problem

Convert the following RA into its equivalent DFA − 1 (0 + 1)* 0

*Solution*

We will concatenate three expressions “1”, “(0 + 1)*” and “0”

Now we will remove the **ε** transitions. After we remove the **ε**transitions from the NDFA, we get the following −

It is an NDFA corresponding to the RE: 1 (0 + 1)* 0. If you want to convert it into a DFA, simply apply the method of converting NDFA to DFA discussed in Chapter 1.

## Finite Automata with Null Moves (NFA – ε)

A Finite Automaton with null moves (FA-ε) does transit not only after giving input from the alphabet set but also without any input symbol. This transition without input is called a **null move**.

An NFA-ε is represented formally by a 5-tuple (Q, ∑, δ, q_{0}, F), consisting of

**Q**− a finite set of states**∑**− a finite set of input symbols**δ**− a transition function δ : Q × (∑ ∪ {ε}) → 2^{Q}**q**− an initial state q_{0}_{0}∈ Q**F**− a set of final state/states of Q (F⊆Q).

## Removal of Null Moves from Finite Automata

If in an NDFA, there is ε-move between vertex X to vertex Y, we can remove it using the following steps −

- Find all the outgoing edges from Y.
- Copy all these edges starting from X without changing the edge labels.
- If X is an initial state, make Y also an initial state.
- If Y is a final state, make X also a final state.

### Problem

Convert the following NFA-ε to NFA without Null move.

*Solution*

**Step 1** −

Here the **ε** transition is between **q _{1}** and

**q**, so let

_{2}**q**is

_{1}**X**and

**q**is

_{f}**Y**.

Here the outgoing edges from q_{f} is to q_{f} for inputs 0 and 1.

**Step 2** −

Now we will Copy all these edges from q_{1} without changing the edges from q_{f} and get the following FA −

**Step 3** −

Here **q _{1}** is an initial state, so we make

**q**also an initial state.

_{f}So the FA becomes −

**Step 4** −

Here **q _{f}** is a final state, so we make

**q**also a final state.

_{1}So the FA becomes −