Enter the regular expressions P and Q into the calculator to solve a linear regular equation using Arden’s Theorem. This is commonly used when deriving a regular expression from a finite automaton by writing and solving state equations.

Arden’s Theorem Calculator

Basic Formula
Regular Equation Solver

Solve the standard Arden form: X = P·X + Q

Related Calculators

Arden’s Theorem Formula

The following formulas are used to solve linear regular-expression equations using Arden’s Theorem (where “+” means union and juxtaposition means concatenation). 

\begin{aligned}
X &= P X + Q,\ \varepsilon \notin L(P)\ \Rightarrow\ X = P^{*}Q \\
X &= Q + X P,\ \varepsilon \notin L(P)\ \Rightarrow\ X = QP^{*}
\end{aligned}

Variables:

  • X is the unknown regular expression (the solution you want)
  • P and Q are known regular expressions
  • ε is the empty string, and ε ∉ L(P) means P does not generate the empty string
  • * is the Kleene star (zero or more repetitions)

To solve the equation, rewrite it in one of the standard forms above and then apply the corresponding solution (either P*Q or QP*).

What is Arden’s Theorem?

Arden’s Theorem is a result in formal language theory used to solve certain linear equations over regular expressions (or, equivalently, regular languages). In its standard form, if P and Q are regular expressions and ε ∉ L(P), then the equation X = P·X + Q has a unique solution as a language, and one regular expression describing that solution is X = P*·Q. (Different regular expressions can still represent the same language.) Arden’s Theorem is commonly used when converting a finite automaton into a regular expression by setting up and solving state equations.

How to Use Arden’s Theorem?

The following steps outline how to apply Arden’s Theorem to solve a regular equation.

  1. Write the equation in a standard form, such as X = P·X + Q or X = Q + X·P.
  2. Identify the expressions P and Q (the “coefficients” and constant term).
  3. Check the condition for uniqueness: ε ∉ L(P).
  4. Apply Arden’s Theorem to obtain the solution: X = P*·Q for X = P·X + Q, or X = Q·P* for X = Q + X·P.
  5. Optionally simplify the resulting regular expression (without changing the language it represents).
  6. Check your result with the calculator above.

Example Problem : 

Use the following as an example problem to test your knowledge.

Equation: X = aX + b

Here, P = a and Q = b

By Arden’s Theorem (since ε ∉ L(a)), the solution is X = a* b