DFAs and NFAs may seem like academic novelties but they are amazingly powerful for certain problems. For example, naively searching a string of length N for P

DFAs and NFAs may seem like academic novelties but they are amazingly powerful for certain problems. For example, naively searching a string of length N for P different substrings will yield an algorithm that has roughly O(N * P) worst case time complexity. But implementing that algorithm as a DFA yields an efficient construction that has O(N) worst case time complexity. This results in considerable speedups for complex pattern recognition tasks on large inputs, and yields other useful properties. As a real world example, a CSV file can be parsed in parallel on a GPU by using a DFA based algorithm [1]. One downside to DFA representations is that they can be difficult to work with as linear text in your editor. Tikz produces great visualizations but I feel the syntax is a bit cumbersome. I’m still searching for that perfect text based format for DFAs - ideally one that can be visualized but also executed. [1] ParPaRaw: Massively Parallel Parsing of Delimiter-Separated Raw Data https://arxiv.org/abs/1905.13415 https://arxiv.org/abs/1905.13415