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.

Improve this question
$\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$
    – Benjamin Steinberg
    Commented 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$
    – François G. Dorais
    Commented Sep 11, 2022 at 22:52

0

Reset to default

You must log in to answer this question.