What is an automaton?

Question

For several times I hear discussions about automata, whether in the chat or in questions/answers. However I particularly do not know what an automaton is, I have no idea to tell the truth. When those images appear then, for me it is "aliens".

I see several "types of automata", such as finite deterministic, finite, cellular, among others.

• What is an automaton?
• What do automata do? What are they for?
• Where the automata live?

Answer 1

Don’t want to know what they [automata] eat or how they reproduce?
Maniero Junior, Antonio, 2017

Automata eat letters/discrete tokens, living in mathematical spaces. A priori, if mathematics does not exist, they are in the imaginary world. If mathematics exists, then they are on the plane of ideas.

They reproduce by spontaneous generation, have no genetic code. Because they have no heredity, they are not subject to evolution

There are entities that have genetic code and this genetic code produces automata. In this sense, the parallel "automaton" with biology would be more like "proteins".

---

What is an automaton?

Automaton, as said above, is a mathematical entity. The etymology of the word comes from the time of self-operated analogue machines. There are self-operated systems since the Hellenistic period, some even prior to that. The only thing you need to keep these systems running is a power source.

A rope clock is a self-operated mechanism. The only thing you need to provide to it is power. You provide this energy by "winding", then this energy is stored in a capacitor through elastic energy and is supplying the mechanism as the energy is needed.

Another example of string automaton is this one:

An automaton that became known in cinema was The invention of Hugo Cabret, who draws scenes from classic films.

Mathematically, automata do not have the physical limitation of needing energy to operate, because in the mathematical world there are no problems with conservation and energy expenditure. They are simply self-serving "mechanisms" that run on top of a entree.

In a typical way, the entree where they work consists of discrete cells, each cell containing a piece of information. Often this information is represented by a number or a letter. The most correct would be to call information symbol, or token information.

How is the input provided through symbols? , how can the automaton identify where information begins and ends and where another begins?

The way this information is passed to the automaton varies. It is usually a semi-infinite tape. They can be multiple semi-infinite ribbons, or even infinite in both directions. But it can be a plane. Or a three-dimensional space. Or even n-dimensional. However it may be, the automaton has one (or more) "head" from which it reads the information. Similar to magnetic HD, which has read/write head information, so the automaton travels interacts with its input.

A semi-infinite tape has the same computational power as an infinite tape for both sides. Imagine a hypothetical situation where a Turing machine is at the beginning of the tape data and "needs" to write something at the beginning of the tape. On an infinite tape he would only need to go an extra position to the left and then write what is needed.

On a semi-infinite tape, however, this is not possible. There is nothing else "left" at the beginning of the data. What could be done in this case would be a shift of ALL tape data one position to the right, writing the desired symbol in as far left as possible. This problem is an instance of Hotel de Hilbert, where it is necessary to accommodate one more guest and he is accommodated on the left. If necessary, it is possible to accommodate more than one guest by moving who is already staying n rooms to the right.

It has some mathematical models that the Turing machine (the most powerful of the automata) has 3 semi-infinite tapes:

1. reading tape, where the head can only read and can only go forward; without writing or back-tracking
2. writing tape, where the head can only write and go forward; no reading or back-tracking
3. work tape, where the head moves at will and where computing takes place; the computer’s RAM would be this "working tape"

This mathematical model offers so much computational power that a Turing machine with only a single semi-infinite tape, where it can perform writing and reading limitlessly and has no limitation of the direction of head motion. The advantage of the model that separates into 3 tapes is that some properties are easier to demonstrate.

What do automata do? What are they for?

The automata are entity that will read the information contained in the reading head, possibly alter some information through the writing head and move the heads in arbitrary directions.

So they read and write. They "just" do it. Usually they have internal state that indicates what to do next.

To represent an automaton, they usually draw through a graph containing the following information:

1. the states (vertices)
2. the transactions (edges)
3. what is necessary for the transaction to occur (edge label)

Depending on the automaton, the information to put on the label may vary. For example, in finite automata (finite tape input, read-only head, every read moves the head one position to the left), it is only necessary to put what information needs to be read to indicate which state change will occur. See below:

In stack automata, you have the input equal to that of the finite automaton and also have a stack from where you can read and write elements into it (but only at the last position). Any reading of the stack implies necessarily removing the last element from the top; if you want to keep the stack intact after a read, you should write that element back into the stack. You may also not read the stack. Just as you can write to the stack without consuming anything. See below:

Look at the first transaction: -,-/S. This indicates 3 things:

1. the trace - before the comma indicates that it simply ignored the input, so this transaction occurs without reading
2. -/S indicates that nothing is read from the stack through the - before the bar; and
3. the symbol S is inserted at its top

Look at the second transaction, -,S/-:

1. again, ignore input with dash
2. it is necessary to have S at the top of the stack, this symbol which, by being read, will be drawn off
3. the stroke after the bar on S/- indicates that nothing is inserted in the stack

Just one more transaction, a,S/SBB:

1. it is necessary to read a of the entrance
2. it is necessary to have S at the top of the stack
3. will be written SBB, in that order, then the next top of the stack is S, then B, and then you’ll have one more B.

On Turing machines of a tape, as the head moves freely, you need to indicate in each transaction:

1. the symbol read (or something to indicate that either)
2. the written symbol (or something to indicate that you will not write)
3. the direction of reading

In the end, the automaton will compute on top of this information. No need for external stimulus, just providing it with input. This computation can be to produce a new value (when the return is contained in some tape/plane/hyperplane of writing) or simply to make a decision; in the case of the decision, the internal state in which the automaton terminates the computation indicates whether it has accepted or refused the input. Returning to the first automaton (the finite automaton):

The following states are of entry acceptance:

1. q0
2. qb1
3. qb2
4. qa

The following state indicates refusal of entry:

1. damnation

This automaton recognizes all words that do not contain the substring bbab. So it doesn’t matter what your input is, if it contains bbab somewhere, she’ll end up in the state damnation and your word will be refused upon reading. Try to run this automaton in hand, you will learn a lot from it.

Where the automata live?

Live in math and nerd heads =D

---

Classification of automata

There are some ways to classify automata. One is to differentiate a processing/computing automaton, where something relevant will be written on the output tape, from the decision automata, where nothing needs to be written and only cares whether its final state is an accepting state or not.

But I prefer to sort them by their computational power (and secondary characteristics of their functioning).

Deterministic finite state machine

Also known as deterministic finite automaton, AFD

These automata are capable of recognizing any regular grammar. No matter how complicated it is, this automaton will recognize it.

Regular expressions (without look Ahead and other strange things) are described by regular grammars, so each regular expression will have its deterministic finite automaton.

They are characterized by:

• any reading advances the reading tape, at all times
• advance (in reading) always, back (in reading) never
• there is no working tape
• knowing the current state and character available in the reading head, i at all times I know the next state, and I know there can only be one
• I can only change status with read (no lambda/empty transactions)

Afds can generate output yes. If the writing on the output tape is determined solely and exclusively by the destination state, then we have a moore machine. If the triggered transaction is responsible for producing the symbol on the output tape, then we have a mealy machine.

Non-deterministic finite state machine without lambda transactions

Also known as nondeterministic finite automaton without lambda transactions, AFN without lambda.

The difference between this automaton and DFA is a relaxation of DFA constraints.

Restriction removed:

• knowing the current state and character available in the reading head, i at all times I know the next state, and I know there can only be one

It is relaxed, allowing for two or more possible destinations for the same read symbol.

Computationally, it may appear to recognize more than the DFA. But this is not true, everything that an NFA without lambda recognizes, there is some DFA that recognizes. That is to say:

• both automata have the same computational power
• an AFD can be obtained from an AFN

Non-deterministic finite state machine with lambda transactions

Also known as nondeterministic finite automaton, AFN.

This automaton allows the existence of state change without consuming symbols of the reading tape. To this state change without consuming reading we give the name of "lambda transaction".

Afns can be reduced to Afds, always. Both have the same computational power.

Later I put:

• pushdown automaton
• queue automaton
• two-stack automaton
• turing machine

Answer 2

Come on, first of all, an automaton is a machine, in which case a robot that mimics the movements of a human being, can be a person or animal, another point, to be an automaton, it can’t act on its own, that is, make its own decisions, all decisions are set automatically (pre-programmed instructions). Second, the use depends on the type of automaton, but in general it is to perform predetermined actions, that is, to make movements, or to speak and third, where do automata live? As stated, automata are machines, so they "live" where they were meant to be, for example: A park dummy who speaks and reaches out while passing a person in front of him, he lives in the park, so on.