Theory of Computation – Construction of Regular Expressions from Deterministic Finite Automata

We know that for every regular expression there exist a deterministic finite automaton. So we can say that regular languages, regular expressions and finite automata are all different representation of the same thing. Earlier we learnt how to convert a regular expression into a finite automaton; in this tutorial we will learn how to convert a given finite automaton to a regular expression. For that we must first learn about Arden’s Theorem.

Arden’s Theorem
Let P and Q be two regular expressions over alphabet Σ. If P does not contain null string, then
R = Q + RP
has a unique solution that is R = QP*
Proof:
Put the value of R in the R.H.S.
R = Q + (Q + RP)P = Q + QP + RP²
When we put the value of R again and again we get the following equation
R = Q + QP + QP² + QP³…..
R = Q(1 + P + P² + P³ + ….
R = Q(є + P + P² + P³ + ….
The second part of the product on the L.H.S can be replaced with the kleen closure. So the equation becomes
R = QP*

Using Arden’s Theorem to find Regular Expression of a Deterministic Finite automata

1. For getting the regular expression for the automata we first create equations of the given form for all the states
   q₁ = q₁w₁₁ + q₂w₂₁ + … + q_nw_n1 + є (q₁ is the initial state)
   q₂ = q₁w₁₂ + q₂w₂₂ + … + q_nw_n2
   . .
   . .
   . .
   q_n = q₁w_1n + q₂w_2n + … + q_nw_nn
   w_ij is the regular expression representing the set of labels of edges from q_i to q_j
   Note: for parallel edges there will be that many expressions for that state in the expression.
2. Then we solve these equations to get the equation for q_i in terms of w_ij and that expression is the required solution, where q_i is a final state.

Assumptions made while forming the regular expression

1. The transition diagram should not have є – transitions
2. It must have only a single initial state

Let us see an example to demonstrate this method

Example: Draw a FA that accepts strings containing exactly 1 over alphabet {0, 1} and write a regular expression for the same.
View Answer

Note: We need not consider a trap state in our equations as it does not contribute to the regular expression

Given below are few questions for you to practice.

Question1: Construct a regular expression corresponding to the automata given below

View Answer

Question 2: Derive a regular expression for the language containing strings ending in 1 but not containing substring 00.
View Answer

Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.