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 −

r [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 −

rr

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.

q

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 −

finite_automata

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 −

a

Problem

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

finite_automata1

Solution

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

Let’s write the below equations −

a

Hence, the regular expression is 0*10*.

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Automata Theory Topics