How Floyd-Warshall is used to convert DFAs to regexes
‹‹ 2022-02-20 ››
It's really fun to find unexpected connections between different areas of knowledge, like how recursion and mathematical induction are essentially the same thing, or how linear independence in vector spaces correlates with cycles in graphs (so much so that you can run Kruskal on either). The topic for today is neither of these, it's actually about how the algorithm that converts a deterministic finite automaton to a regular expression is actually very very similar to Floyd-Warshall's shortest path algorithm. Let's start with the automata, shall we?