regex – Applying simplification rules to a DFA to derive a regular expression for it

It is quite straightforward once you see it:

The equation of 𝑋₁ is right there inside the equation of 𝑋₃:

      𝑋₁ = 𝑎𝑋₂ + 𝑏𝑋₁

      𝑋₃ = 𝑎𝑋₂ + 𝑏𝑋₁ + 1

Note how the right-hand side of the first equation occurs also in the last equation, so in the last equation you can replace it with 𝑋₁, giving you:

      𝑋₃ = 𝑋₁ + 1

Another way to see is it is to subtract the first equation from the last one (each side of the equation), which gives

      𝑋₃ − 𝑋₁ = 1

…and after you move the negative term to the other side, you have the expected result.

Continuation

After this step, we have:

      𝑋₁ = 𝑎𝑋₂ + 𝑏𝑋₁

      𝑋₂ = 𝑎𝑋₂ + 𝑏𝑋₃

      𝑋₃ = 𝑋₁ + 1

and the simplification can continue further. In the second equation we can substitute 𝑋₃ with its simplified definition, and omit that latter definition:

      𝑋₁ = 𝑎𝑋₂ + 𝑏𝑋₁

      𝑋₂ = 𝑎𝑋₂ + 𝑏𝑋₁ + 𝑏

And again we find a similar situation: the righthand side of the first equation occurs in the second one, so we can simplify the second equation:

      𝑋₁ = 𝑎𝑋₂ + 𝑏𝑋₁

      𝑋₂ = 𝑋₁ + 𝑏

In a next step we can substitute that simplified definition of 𝑋₂ into the first equation:

      𝑋₁ = 𝑎𝑋₁ + 𝑎𝑏 + 𝑏𝑋₁

This simplifies to:

      𝑋₁ = (𝑎+𝑏)𝑋₁ + 𝑎𝑏

And applying Arden’s rule this can be written using the Kleene star as:

      𝐿₁(𝐴) = (𝑎+𝑏)*𝑎𝑏

In words: any sequence of the symbols 𝑎 and 𝑏 that ends in 𝑎𝑏.

As a side note: in a programming environment, in regex syntax, you would write it as:

[ab]*ab