Theory of Digital Automata

Automata theory is a branch of discrete mathematics that studies abstract automata — computing machines represented as mathematical models — and the problems they can solve.

Automata theory is most closely related to the theory of algorithms: an automaton transforms discrete information step by step, at discrete moments in time, and produces the result step by step according to a given algorithm.

There is an algebraic treatment of automata theory that uses semirings, formal power series, formal tree series, fixed-point theory, and matrix theory .

Terminology

Symbol is any atomic (that is, indivisible without further loss of meaning) unit of data that can produce an effect on the machine. Most often a symbol is a letter of some formal language. For example, the symbols used in many programming languages include letters of the ordinary language, delimiters, and various additional signs. But a symbol can also be, for example, an entire keyword of some programming language (if, for, while, etc.), a graphical element of a diagram, and so on.

• Word is a string of symbols created through concatenation (joining).
• Alphabet is a finite set of distinct symbols (a set of symbols)
• Language is a set of words that can be composed (generated) from the symbols of a given alphabet. A language may be finite or infinite.

Purpose of formal automata

In automata theory, this word is understood as a formal (mathematical) construction that defines an algorithm whose purpose is to determine whether a given word belongs to the input language described by this formal automaton. The word “formal” emphasizes the difference between such an automaton and automatic machine tools embodied in metal, automatic transmissions, and other similar devices. For brevity, in the relevant textbooks the adjective “formal” or “mathematical” is often omitted (starting with the name of the theory itself — it would be more accurate to say “theory of formal automata”) when it is clear what is meant.

Operation of the automaton

To fulfill their purpose, all (formal) automata are endowed with the property of being in some admissible state and with transition functions of the automaton, which in the simplest case (finite automata) define only the possibility of transitioning from one state to another when reading the next symbol from the input string. After each transition, the automaton's reading head shifts by one symbol (it is “read”). This continues until the end of the word being read is reached, or no suitable transition function is found.

The set of all admissible states of the automaton is finite and forms the state alphabet of the automaton. From the entire set of states, a subset of initial states of the automaton is distinguished (in one of which the parsing of a word may begin), and a subset of terminating (or final) states, in which the automaton (if the word has by then been read in full) can conclude that the word being parsed (the input word) belongs to the language of the automaton. The initial and final states of the automaton may overlap. Reaching a terminating (or final) state merely indicates the possibility of completing the parse, that is, during operation the automaton may pass through a given final state multiple times while the reading of the word continues.

Start and end of automaton operation

The start of the automaton's operation is completely determined by its “initial configuration”, which includes the word being parsed and the state the automaton is in. If the automaton is in one of the initial states and there is a transition function for that state and the first symbol of the string being read, the automaton makes the corresponding transition, shifts the reading head on the input word, and (in the simplest case — finite automata) moves on to examine the next input symbol.

For an automaton to accept (or, as it is said, admit) an input word, two conditions must be satisfied:

1. The input word must be read completely
2. After reading the word, the automaton is in (or can reach, via empty transitions, if such are allowed for the corresponding type of automaton) one of the terminating states. For some types of automata this criterion may be formulated somewhat differently, and automata theory proves that such halting formulations are equivalent (interchangeable).

Here, by “empty transition” or “transition on an empty symbol” is meant a transition from one state to another in which the next symbol of the input word is not read, or, in other words, an empty symbol is “read”. See the notation below.

Note that the automaton must accept all valid words of the language it describes, while not accepting any word that does not belong to that language.

If the input word does not belong to the language, then the automaton either

1. will stop after a finite number of steps, without having read the word to the end and without having a suitable transition function to continue reading
2. will read the word in full, but will not be in one of the terminating states (or some other equivalent criterion will not be satisfied for certain types of automata)
3. will enter an infinite cycle of changing admissible states, in which, however, both criteria for accepting (admitting) the word will never be satisfied simultaneously.

Main types of automata

By the complexity of the languages parsed

Formal automata are usually classified according to the features of their transition functions, which determine the degree of complexity of the language they describe.

According to N. Chomsky's classification, four main types (by variety, by complexity) of formal languages are known:

1. Regular
2. Context-free
3. Context-sensitive
4. Unrestricted languages (without additional restrictions)

For parsing words from regular languages, formal automata of the simplest design are suitable, the so-called finite automata. Their transition function only defines a change of state and, possibly, a shift (reading) of the input symbol.

To parse a word from context-free languages, a “pushdown tape” or “stack” must be added to the automaton, onto which a string based on the corresponding stack alphabet is written at each transition. Such automata are called “pushdown automata”.

For context-sensitive languages, even more complex linear-bounded automata have been developed, and for unrestricted languages — the Turing machine .

On closer acquaintance with the theory, it becomes clear that the more complex the design of the automaton, the greater its recognition capabilities, but at the same time it also becomes more complex and labor-intensive to work with. Therefore, a competent mathematician or software engineer tries to choose the simplest type of automaton that solves the given recognition task with adequate quality.

Note that many information-retrieval tasks on the World Wide Web are formulated in terms of regular languages (that is, with the strictest restrictions), while most of the widely used general-purpose programming languages are quite successfully implemented on the basis of context-free grammars (albeit with some enhancements, see “attribute grammars”). Among the few and rather peculiar exceptions is the programming language LISP, developed on the basis of context-sensitive languages. As for the Turing machine, despite all its (theoretical) universality and power, it turns out to be so complex and inconvenient for use in applications that it is used only for theoretical analysis.

On the uniqueness of the transition function

For one and the same current configuration (the state of the automaton, the input symbol being read, and possibly some additional parameters for complex types of automata, for example, the contents of the stack in a pushdown automaton), the transition functions of a formal automaton can specify either a single (definite, deterministic) transition or several different ones. In other words, for one and the same configuration of the automaton, several transition functions may, generally speaking, exist.

Indeterminacy (non-determinism) of an automaton can also arise when each of its configurations corresponds to only one transition function, but transitions on an “empty string” (empty symbol) are also allowed. It is clear that ambiguity of transition here can arise not in one, but over several clock cycles of the automaton's operation.

By this feature, automata are also divided into deterministic (definite) and non-deterministic. The importance of this division is also explained by how the property of determinism affects the interpretation of an automaton's acceptance of a word.

Thus, if we have a deterministic automaton, then if the above-mentioned conditions for accepting a word are not satisfied, we can immediately say that the given word does not belong to the language. If, on the other hand, our automaton is non-deterministic, then in such a case we draw this conclusion only for one of the possible branches of parsing the word. In practice, the programmer has to somehow keep track of all the possible branch points in parsing the word and, if one of the branches fails, backtrack to the next branch point and explore another parsing branch. Only after examining all possible parsing variants (if none of the intermediate branches satisfied the acceptance conditions) can one confidently conclude that the given word does not belong to the language.

It is clear that tracking and accounting for possible backtracking while parsing a word noticeably complicates the programmer's work. This raises the question of whether an automaton can be transformed so that it changes from non-deterministic to deterministic and, in a whole range of cases, therefore becomes more convenient to work with. In automata theory it has been proven that for regular languages and their corresponding finite automata this can always be done. But for the remaining types of languages (according to N. Chomsky), starting with context-free languages and their corresponding automata, in the general case — this is no longer possible.

On the other hand, it is noted that non-deterministic automata are usually noticeably smaller in size, and their operating logic is more easily understood by a person. Note that when using multiprocessor (multicore) computing machines, the very possibility of parallelization is often closely tied to the non-determinism of the algorithm. A program, all of whose parts must be executed in a strictly defined sequence, does not lend itself to parallelization… .

Examples of formal definitions for finite automata

Automata can be deterministic and non-deterministic.

Deterministic finite automaton (DFA) — a sequence (tuple) of five elements (𝑄,Σ,𝛿,𝑆₀,𝐹) , where:

• 𝑄 — the set of states of the automaton
• Σ — the alphabet of the language that the automaton understands
• 𝛿 — the transition function, such that 𝛿:𝑄×Σ→𝑄
• 𝑆₀∈𝑄 — the initial state
• 𝐹⊆𝑄 — the set of final states.

Non-deterministic finite automaton (NFA) — a sequence (tuple) of five elements (𝑄,Σ,Δ,𝑆,𝐹) , where:

• 𝑄 — the set of states of the automaton
• Σ — the alphabet of the language that the automaton understands
• Δ — the transition relation, Δ={<𝑞,𝑎,𝑝>:𝑞,𝑝∈𝑄,𝑎∈Σ∪{𝑒}} , where {𝑒} — the empty word. That is, an NFA can make a transition from state q to state p, unlike a DFA, via the empty word (that is, without reading the next symbol from the input), and can also transition from q on a into one of several states (in a DFA, a transition from q on a is possible into at most one state from Q, hence the definiteness (or, in English, determinism) of all transitions of such an automaton and its name).
• 𝑆⊆𝑄 — the set of initial states
• 𝐹⊆𝑄 — the set of final states.

Word

The automaton reads a finite string of symbols a₁, a₂, …., a_n , where a_i ∈ Σ, which is called the input word. The set of all words is written as Σ*.

Accepted word

A word w ∈ Σ* is accepted by the automaton if q_n ∈ F.

A language L is said to be read (accepted) by an automaton M if it consists of words w over the alphabet Σ such that, when these words are fed into M, upon completion of processing it arrives at one of the accepting states F:

𝐿={𝑤∈Σ⋆|𝛿^(𝑆₀,𝑤)∈𝐹}

Usually the automaton moves from state to state by means of the transition function 𝛿, reading one symbol from the input in the process. There are automata that can move to a new state without reading a symbol. A transition function that does not read a symbol is called an 𝜖-transition (epsilon transition).

Applications

Automata theory underlies all digital technologies and software; for example, a computer is a specific instance of the practical implementation of a finite automaton.

Part of the mathematical apparatus of automata theory is directly applied in the development of lexical and syntactic analyzers for formal languages, including programming languages, as well as in building compilers and developing programming languages themselves, hardware description languages, and markup languages.

Another crucial application of automata theory is the mathematically rigorous determination of the decidability and complexity of problems.

Typical problems

• Construction and minimization of automata — the construction of an abstract automaton from a given class that solves a given problem (accepts a given language), possibly followed by minimization of the number of states or the number of transitions.
• Synthesis of automata — the construction of a system from given “elementary automata” that is equivalent to a given automaton. Such an automaton is called structural. It is applied, for example, in the synthesis of digital electrical circuits on a given element base.

See also