4
$\begingroup$

Kleene's theorem that finite automata (specifically, nondeterministic) are expressively equivalent to regular expressions seems to be a powerful and not immediately obvious tool for untangling the state diagrams of NFAs (by translating an NFA to a regular expression and back).

Has this been found to have applications within pure mathematics? I could imagine it having something interesting to say, for instance, about the generation of monoids.

This has been difficult to search for, on account of so many theorems being named after Kleene.

$\endgroup$
2
  • $\begingroup$ In my experience most pure math things with a proof using regular expressions also has a straightforward automaton or semigroup proof. But sometimes the regular expression proof is easier for induction $\endgroup$ Sep 11, 2022 at 20:54
  • $\begingroup$ Not exactly what you're looking for but Brzozowski’s minimization algorithm is incredibly interesting. It evidently depends strongly on Kleene's theorem but that is often taken as a matter-of-fact in descriptions and applications of Brzozowski’s algorithm, so you might not find the connection in casual search. $\endgroup$ Sep 11, 2022 at 22:52

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.