LaTeX Finite Automata and State Diagrams with Tikz | Hacker News Reader

LaTeX Finite Automata and State Diagrams with Tikz

hayesall.com

108 pointsbjourne35 comments

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

But implementing that algorithm as a DFA yields an efficient construction that has O(N) worst case time complexity.

I think it is worth saying that this is possible because finite state automata have a set of useful, well-understood operations, like concatenation, union, intersection, negation, kleene closure, determinization, and minimization. This makes it possible to generate complex automata from basic building blocks and to make them deterministic and minimal.

> DFAs and NFAs may seem like academic novelties but they are amazingly powerful for certain problems.

They are the same thing as regular expressions. It's safe to say they're not being dismissed as academic novelties.

Is that your research? I will have to read up more on it, but I am blown away that it is even possible to do that.

I always used this website to generate them https://madebyevan.com/fsm/

For people who don't know, this tool was created by the CTO of Figma and the creator of ESBuild

This looks like just the tool i needed for a proyect I have due in a couple of week! Thanks!

On this topic, I recently came across a nice string diagram formalization for automata: https://arxiv.org/pdf/2009.14576.pdf

Neat.

If I understand correctly, their work makes diagrams and code isomorphic. Meaning roundtripping between diagrams and code can be done with no loss, no impedance mismatch.

Meaning my long-time dream of a two-way structure editor is now feasible. Edit the diagram, the code updates. Edit the code, the diagram updates. Back and forth.

As you know, the Achilles Heel of CASE tools (and visual programming) has been the inability to roundtrip.

Do I understand correctly?

My science-fu is weak. I've been struggling to wrap my head around grammars and whatnot my entire career. Please forgive.

Over the past ~25 years there has been a concerted effort to use the tools of category theory (a branch of mathematics) to develop unambiguous diagrammatic languages, and this paper is a good example of the results of that effort. I’m personally quite intrigued by where this could go, but there’s still a lot of work to do before it revolutionizes the way code is written.

If you want to go down some rabbit holes, check out the homepage of the Mathematically Structured Programming group at the University of Strathclyde: https://msp.cis.strath.ac.uk/index.html

One of the elephants in the room of laying out node-arc diagrams is just how bad Graphviz is at the task. This sort of thing should be a core use case for Graphviz and it just isn't a good tool.

If anyone writes a Graphviz tutorial, it would be doing the world a service to prefix it with "But seriously, note that Tikz exists".

Do you mean that the graphs don't look good? They layout seems good, to me.

I have a Theory of Computation text so I have many, many such diagrams. I don't rely on the graphviz output directly. If I have to make a graph where the layout isn't obvious then I write a .dot file and run it through graphviz, specifically, neato. I use that as a model for drawing it with a LaTeX tool (I don't use TikZ, I use Asymptote, but the point is the same). That way I get a pretty good layout, better then I personally could do without the guidance from graphviz, and a visual consistency to the diagrams.

I've never really liked the look of the Tikz-generated automata. Something about them always looks a little off to me. I also dislike the use of 0 and 1 as the canonical alphabet. a and b look nicer, they stand out better in written instructions and solutions (when typeset using math mode), and (this sounds silly) sound nicer when talking about them with the class. Using 0 and 1 seems to imply some connection to binary that is not really there and probably confuses or misleads some students.

Of course, everyone will have a different opinion on such aesthetic matters. I taught an undergrad comp theory course for a decade or so and I wrote my own similar package[1] for generating diagrams using Metapost that built on the standard boxes package. Students were able to learn the system pretty quickly and the results were usually good, though it was pretty easy to pick out which students did/did not care about how things look.

[1] - https://github.com/russross/automata/

Nice overview. One small nitpick: `right of=<label>` is deprecated, instead you should use `right=0cm of <label>` (after loading the `positioning` library), which is more flexible. If you don't want to specify the distance, there is also `right=of <label>`. See 17.5.3 in the manual.

I loved using Tikz for my Discrete Math homework. I was so proud of how pretty the DFA's looked :)

The TikZ style should really be the default standard or even the bottom line. Last time I check Google Slides still doesn't understand how to connect two blocks of texts. I have to manually choose among four points (north/south/west/east of a block) to start or end a line. Whereas in TikZ the optimal point (among infinitely many points that constituent the border) is chosen.

I used OmniGraffle and got some pretty fine looking graphs myself, but this is next-level ease. I’m jealous that you knew how to use this.

I used tikz to make figures when I decided typesetting some of my physics notes was a good idea. Like any programming language/dsl, you start small and work your way up. Fortunately, there were a ton of examples and the manual is gigantic

How does this compare to Penrose?

Also, has anybody tried using Inkscape [1,2] or another vector drawing tool for this? I imagine it would be faster and more intuitive than learning Tikz.

[1] - https://stackoverflow.com/questions/17610717/drawing-an-undi...

[2] - The following appears to be part of a presentation: https://gould.cx/ted/presentations/txlf16/Technical%20Drawin...

I briefly looked at their website recently, and it looked to me like Penrose just renders the diagram interactively as a webapp. I didn't see a "compiler" that would translate the diagram code into a standalone PDF/PNG file that would be easy to include in a LaTeX document.

I find manually laying out graphs and digraphs tedious.

It seems like a problem that should be amenable to machine learning approaches. Basically, training a machine as to what is an aesthetically pleasing layout and what is not.

Are there layout engines that use machine learning for layout, as against being implemented in terms of specific tree or graph layout algorithms?

It would be nice if there were a tool that would take the input to graphviz, run it to graphviz to get the layout and then use that to generate the tikz code using that layout.

Years ago I wrote and contributed a backend to graphviz that output MetaPost (I just had a look and don't see it in the source anymore). It was very easy; I found another backend and made a few tweaks. Perhaps you might have a look?

TikZ/PGF had a graph layouting implementation for about a decade now, c.f. "Part IV - Graph Drawing" in the manual. And apparently `dot2tex` can also render TikZ instructions, so going via Graphviz is possible too.

TikZ claims some support for automated graph layout generation in chapter 26 of the manual [1]. It also lets you specify your own graph layout algorithms in Lua. Results in my experience aren't as aesthetic or intuitive as a custom layout but are comparable to graphviz.

[1] https://tikz.dev/gd-overview

edit: chapter 27 in the online version

Arguably a graph layout is performed by a kind of "training" in the sense that it takes many iterations for the parameters (and possibly physical distancing forces) to be evaluated for every node against all of the others. This is a solver, and not entirely unlike something like gradient descent. This is painting a rather broad brush with these terms, however.

I don't think the difficulty in making diagrams has to do creating a layout that is aesthetically pleasing, but rather with expressing ideas visually in a way that others can understand them. I'm sceptical that AI can help with that.

I'm pretty confident that it could be a good improvement over the currently used spring models. Give me three high-distance options that ML thought were good, I'll probably choose one over laying out manually.

Relevant search term: graph planarisation

So repulsed by this. Learning custom DSL with opaque semantics that will leave you scratching your head when something goes wrong and tool behaves not like you expect. Why people opt into such tools at all?

Because those tools are well-known and they allow people to get the result they want. They also can be used for other things and are not specific to a particular kind of drawing.

Tikz also allows a tight integration to LaTeX documents that no external tools achieve so easily. The drawing inherits colors and fonts, and bits can be reused across the document and can be shared with other documents too.

High learning curve but long term efficiency with quality results.

Tikz is not perfect but it has the great characteristic of existing.

TikZ & pgfplots are really nice if you get over the initial learning curve and prefer programmatically defining things rather than drawing by hand.

E.g. in my theses all figures (except one in my first thesis) were made with TiKZ with colors and definitions defined in a file that is "imported" during compilation.

This allowed me to fine tune various parts (colors, ...) without having to touch each figure again. Also, all the data files are stored as CSV and read/processed by LaTeX. Between handing in my thesis and publishing the short-paper version of it for a conference I could rerun my analysis (to include the most recent data) with a single command and then just recompile the document to have all figures updated.

The thesis: https://www.ac.tuwien.ac.at/files/pub/hinteregger_18.pdf

And TikZ graphics play somewhat nice with the beamer package. I found it easier to define transitions in technical figures with TikZ/beamer than with PowerPoint or any other tool so far.

In a summer internship I worked on the documentation of a project that tried to optimize pillar-placement for skilifts. This was very Math/Physics heavy.

With TikZ I could define various parts (e.g. pillar, rope, gondola) as "function" and then create figures that combined these parts.

I.e: - place pillars at these locations - connect them with ropes obeying some formula - put gondolas along the rope with some defined distance

Important points where marked with coordinates automatically, allowing explanatory nodes (text box with arrow or paths with labels) to be added (with full LaTeX support).

Cause it looks absolutely beautiful.

I cannot disagree. I was a fan of pic in the past for its much superior (IMHO) syntax, but I also envied tikz beautiful results (for it's based on tex rather than troff).

I haven't looked at that field for a good while but I'm still genuinely interested. And so I'd like to better understand your comment. It is unclear to me whether you are arguing in favor of using another similar tool using a better syntax, or using an automatic graph layout engine, or a manual general purpose vector drawing tool. How would you recommend one to draw such diagrams?

Because it's the same tool that you're already writing the paper in.

Reply on news.ycombinator.com