What is automata theory? A brief introduction.

Shivam Trivedi
Sep 2, 2018 · 3 min read

Automata (automaton — singular) is a machine, an abstract machine using them we can solve crucial computational problems. Automata theory is sub-branch is theoretical computer science and discrete mathematics.

Basically, why do we need a machine [a computer is a machine]? The simple answer is for solving the algorithms and do the computation. Now, how can we solve any algorithm? The simplest method is to solve it by our self. Starts with some input and following a step-by-step procedure to get the output. Another way is to design some machine who perform this operation as per our command.

Why do we need automata when we have computers?

The actual computers are very complicated and difficult to understand. Moreover, its hardware would not be useful, because it would have to be changed every time or enhanced. Whereas abstract machines are simple to understand and quite ideal. We do not require any kind of hardware specifications to build abstract machine because they do not physically exist. We can define them using various mathematical models.

The more the simple machine is the power of it would be less. Even though the simplicity, they are worth learning. They can simplify the mathematical computations which we can use in our theory to solve real-time problems.

What are those machines?

The simplest machine is called a finite automaton or finite state machine. It is running on a very basic principle.

“Any system that is at each moment in one of a finite number of discrete states, and moves among these states in a predictable way in response to individual input signals, can be modeled by a finite automaton.”

The advance and popular machines are defined below:

  1. Pushdown automata
  2. Turing machine [Used in World war 2]
  3. Linear bounded automata

What is the automata theory?

Automata theory is a theoretical concept of each automaton. After learning automata theory you will be able to answer such a question:

# Which class of formal languages is recognizable by some type of automata?

# Are certain automata closed under union, intersection, or complementation of formal languages?

# How expressive is a type of automata in terms of recognizing a class of formal languages? And, their relative expressive power?

# Does an automaton accept any input word?

# Is it possible to transform a given non-deterministic automaton into deterministic automaton without changing the recognizable language?

# For a given formal language, what is the smallest automaton that recognizes it?

Source: Wikipedia

Example:

This is the pictorial representation of the simplest automaton, finite state automaton. After learning the concept you will be able to answer this question. Is this machine accept a string which starts with 01 and contains sub-string 012?

Where can we use these machines?

The formality of automata theory can be applied to the analysis and manipulation of actual human language as well as the development of human-computer interaction (HCI) and artificial intelligence (AI).

Biology is basically theoretical science. But it is complex when we add some computation and mix up it with biotechnology. Life science or genetic science is based on computation. Traditionally, the intricacy and variation found in life science have been attributed to the notion of natural selection. Species become “intentionally” complex because it increases their chance for survival.

“For example, a camouflage-patterned toad will have a far lower risk of being eaten by a python than a frog colored entirely in orange. This idea makes sense, but automata theory offers a simpler and more logical explanation, one that relies not on random, optimizing mutations but on a simple set of rules.”

In short, automata theories can bring a simpler solution to any biological problems.

Any field which has complexity in it can be solved by automata theories, they provide an easy and understandable solution.

“The modern-day pioneer of cellular automata applications is Stephen Wolfram, who argues that the entire universe might eventually be describable as a machine with finite sets of states and rules and a single initial condition. He relates automata theory to a wide variety of scientific pursuits, including: Fluid, FlowSnowflake and crystal formation, Chaos theory, Cosmology, and Financial analysis.”


Originally published at www.quora.com.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade