# Arden's Theorem - Automata Theory

## What is Arden's Theorem?

You can use Arden’s Theorem to find out a regular expression of a Finite Automaton with the properties of regular expressions.

### Statement −

Let’s assume that P and Q be two regular expressions.

Incase if P does not include a null string, then R = Q + RP has a unique solution that is R = QP*

Proof − [After putting the value R = Q + RP]

= Q + QP + RPP

If you include the value of R recursively repetitively then you will get the following equation − It’s proved.

## Assumptions for Applying Arden’s Theorem

• The transition diagram must not have NULL transitions
• It must have only one initial state

### Method

Step 1 – Now create equations in the below mentioned form for all the states of the DFA having n states with initial state q1. Rij represents the set of labels of edges from qi to qj, if no such edge exists, then Rij = ∅

Step 2 − Solve these equations to get the equation for the final state in terms of Rij

### Problem

Let’s construct a regular expression related to the automata given below − ### Solution −

Here the initial state is q2 and the final state is q1.

The equations for the three states q1, q2, and q3 are as follows − ### Problem

Let’s construct a regular expression related to the automata given below − ### Solution −

Here the initial state is q1 and the final state is q2

Let’s write the below equations − Hence, the regular expression is 0*10*.

## Automata Theory Related Practice Tests

Automata Theory Topics