# Finite Automata

A finite automata is a 5-tuple (Q, Î£, Î´, q_{0}, F), where

- Q is a non-empty finite set called states.
- Î£ is a non-empty finite set called alphabet.
- Î´ : Q Ã— Î£ â†’ Q is the transition function.
- q
_{0}âˆˆ Q is the start state. - F âŠ† Q is the set of accept states.

**Non-Deterministic Finite Automata (NFA)**

When the machine is in a given state and reads the next input symbol, we know the next state (using transition), i.e. it is determined. This is called deterministic computation. In a non-deterministic machine, several choices may exist for the next state at any point. Also, the automation can choose to make a transition from one state to another without reading any symbol. This type of transition is shown below.

Formally, a non-deterministic finite automation is a 5-tuple (Q, Î£, Î´, q_{0}, F), where

- Q is a non-empty finite set of states.
- Î£ is a non-empty finite alphabet.
- Î´: Q Ã— Î£
_{Îµ}â†’ P(Q) is the transition function. Also, Q Ã— Î£ â‡’ 2^{Q}. - q
_{0}âˆˆ Q is the start state. - F âŠ† Q is the set of accept states.

For example, NFA drawn below can be formally written as:â€“

- Q = {q
_{1}, q_{2}, q_{3}, q_{4}} - Î£ = {0, 1}
- Î´ is given as

- q
_{l}is the start state. - F = {q
_{4}}

Step of type (i): *a*

Step of type (i): *b*

* *

Step of type (ii): *a*/*b*

Step of type (iv): (*a*/*b*)*

Step of type (iii): (*a*/*b*)*a

* *

Figure 1 : Steps in constructing an NFA^{E}^{ }for (*a*|*b*)**a*

Some important points to remember**:**

- Any DFA is also an NFA.
- For each NFA, there exist an equivalent DFA.
- Taking into account above two points, a language is regular if and only if some NFA recognizes it.
- If n is the number of states in NFA, then the equivalent DFA will have 2
^{n}state including Ï† state.

# Converting NFA to DFA

Letâ€™s have a look at the NFA(N) below that we will be converting in DFA(D).

To construct a DFA(D) that is equivalent to N, we first need to determine Dâ€™s states. Since N is having 3 states, Dâ€™s states will be 2^{3} = 8. Now label each of Dâ€™s state with the subset of Nâ€™s state. Thus Dâ€™s state set is

{Ï†, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

The start state of D is the state that are reachable from 1 by travelling along Îµ arrows. An Îµ arrow goes from 1 to 3, so start state is {1, 3}. Accept states of D are the states containing Nâ€™s accept state, i.e. {{1}, {1, 2}, {1, 3}, {1, 2, 3}}.

Now, we determine Dâ€™s transition function. In D, state {2} goes to {2, 3} on input a, because in N, state Z goes to both 2 and 3 on input a and we canâ€™t go farther from 2 or 3 along Îµ arrows. State {2} goes to {3} on input b. Similarly, state {1} goes to Ï† on input a, because no a arrows exit it in N. Continuing in this way, we obtain the diagram of D.

The above DFA can be simplified by removing the unwanted states. In this case, they are {1} and {1, 2} because there are no arrows pointing at these states and also none of them are start state and hence they canâ€™t be reached. So, the simplified DFA will be