An Introduction to Automata
Why are automata so interesting? Automata are so simple that they fit in many places and situations.
Luca Marx
A blog about automata theory
Latest posts
Regular Expressions & Brzozowski Algorithm
Regular expressions are an algebraic notation to describe regular languages. They can be converted into minimal deterministic finite automata with the elegant Brzozowski algorithm.
Weighted Automata
Automata can be generalized by adding weights to transitions. This way they can compute more complicated functions than just predicates.
Spectral Learning
How can we build a weighted automaton that does what we want it to do? Does there exist a high level language to program automata? What if we could just learn them?
Automata & Real Functions
If we encode real numbers as strings then we can use spectral learning to model real functions as weighted automata.
Automata & Matrix Product States
Looking closely at weighted automata we see that they resemble models used in quantum many body physics.
The DMRG Algorithm
The density matrix renormalization group algorithm is the workhorse for simulating one dimensional quantum systems on a lattice. The interesting thing is that it can be used also for machine learning tasks.
DMRG for Classification
Having seen how DMRG works we apply it to some classification tasks.
ChatGPT, Marshall McLuhan & the end of the world
Why is ChatGPT so unsettling? Are we as humans in danger of being marginalized by AI? We definitely need Marshall McLuhan's help.
The tale of the strange coffee vending machine
Where I want to convince you that coffee vending machine are more interesting than they look.
Automata & Parallelism
Weighted automata have a peculiar kind of parallelism. In this post we will see how to exploit it to evaluate a function over many arguments at once, this will lead to a "poor-man's" version of Deutsch-Jozsa algorithm.
The Automatic Deutsch-Jozsa Algorithm
Last time we saw a parody of the Deutsch-Jozsa algorithm that used automata to evaluate a function over all of its arguments at once. Today I want to show you how it can be made more serious and how it compares to the true quantum algorithm.
The Automatic Grover Algorithm
Last time we devised a recipe to turn quantum algorithms into automata based ones and used it on the Deutsch-Jozsa algorithm. But why stop there? Let's automatize Grover's algorithm too.
Power Series & Quantum States
In the last few posts we saw a mysterious analogy between formal power series and quantum states, it's time to dig into it.