When we talk about Theory of Computation, we talk about the branch of Computer Science that deals with the set of problems that can be solved using an algorithm, providing a model of computation.

When we have a problem, the Theory of Computation permits us to answer questions like:

  • Could be the problem solved algorithmically?
  • If the answer of the above question is yes, how efficiently can be solved?
  • Could exists a precise solution of this problem? Or only an approximative one?

In this post we are going to learn something about automata theory, a subfield of Theory of Computation.

Some programs that you use everyday need to find occurrences of a string in a text.
Think about your preferred IDE or simply any text-editing program.
When you misspelling a variable name and you want to fix this, you need to find all the part of the text where the name is present and substitute it.

Giacomo Zanatta

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store