Calculate Arden’s theorem solutions for regular equations X = P·X + Q or X = Q + X·P and get the equivalent regular expression solution.

Find the least language solution P*·Q. Enter the known expressions P and Q.

Letters/digits, + or | for union, concatenation, *, parentheses, ε for empty string and ∅ for empty language. Spaces are ignored.

Example: a+b. Use ε, eps, epsilon, λ or lambda for the empty string. Do not enter the unknown variable.

Variable label

Default X. One uppercase letter, optionally followed by digits; this label must not occur in P or 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).

X & = P X + Q, ε notin L(P) Rightarrow X = P × Q \ X & = Q + X P, ε notin L(P) Rightarrow X = QP ×

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. Select the equation form, enter P and Q, and select Calculate. Use letters or digits as symbols, + or | for union, concatenation, *, parentheses, ε for the empty string, and ∅ for the empty language. The calculator checks whether P generates ε. If it does, the result is the least language solution; uniqueness is not guaranteed.

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