Talk:Tagged Deterministic Finite Automaton

Figure 2 and associated text provides incorrect epsilon closure for leftmost greedy algorithm

Figure 2 under TDFA construction shows an example flow of epsilon closures for regex a*tb*|ab. It, and the text in the article next to it, shows the closure resulting from active set {q0} as 2, 5, 8, 11. However, the actual leftmost greedy algorithm described in [1] would give result 2, 5, 11, 8 for the automaton in Figure 1. Is this a mistake, or is this figure for a different disambiguation algorithm (e.g. POSIX)? I realize that it's a very minor issue, but it resulted in a few hours of extra debugging for me, so it should probably be clarified. Tagging @Skvadrik as they created the figure. Lisa Felidae (she/her) (talk) 04:18, 24 November 2025 (UTC)

You are right, and I will fix it (in this figure and in TDFA construction below). I guess this was just a mistake, as I constructed the figures manually to make them look nicer - a graph autogenerated by re2c for this example has the correct order. Thanks for reporting! ~2025-36029-04 (talk) 07:01, 24 November 2025 (UTC)

You might have to update Figure 3 as well, it also shows 2, 5, 8, 11 Lisa Felidae (she/her) (talk) 07:42, 24 November 2025 (UTC)

Both figures should be fixed now. Skvadrik (talk) 22:10, 24 November 2025 (UTC)

Thank you! I also updated the article text to align with the new figures. Lisa Felidae (she/her) (talk) 01:43, 25 November 2025 (UTC)

Awesome, thanks. Skvadrik (talk) 06:31, 25 November 2025 (UTC)