Advantages and disadvantages (преимущества и недостатки).

DFAs are one of the most practical models of computation, since there is a trivial linear time, constant-space, online algorithm to simulate a DFA on a stream of input. Given two DFAs there are efficient algorithms to find a DFA recognizing (автомат DFA является одной из наиболее практичных моделей при проведении вычислений, поскольку имеется тривиальное линейное время, постоянное пространство, онлайновый алгоритм для моделирования автомата DFA на входном потоке. При наличии 2-х автоматов DFA имеется эффективный алгоритм нахождения автомата DFA, который распознает):

• the union of the two DFAs (объединение 2-х DFA);

• the intersection of the two DFAs (пересечение (конъюнкция) 2-х DFA);

• complements of the languages the DFAs recognize (дополнительные коды языков, которые признает DFA);

There are also efficient algorithms to determine (имеются также эффективные алгоритмы для определения):

• whether a DFA accepts any strings (принимает ли DFA любую строку);

• whether a DFA accepts all strings (принимает ли DFA все строки);

• whether two DFAs recognize the same language (принимает ли DFA тот же самый язык);

• the DFA with a minimum number of states for a particular regular language (DFA с минимальным числом состояний для особого регулярного языка).

In theoretical computer science, a regular language is a formal language (i.e., a possibly infinite set of finite sequences of symbols from a finite alphabet) that satisfies the following equivalent properties (в теории компьютерных наук регулярный язык является формальным языком (то есть, возможным бесконечным набором конечных последовательностей символов из конечного алфавита), который удовлетворяет следующим эквивалентным свойствам):

• it can be accepted by a deterministic finite state machine (он может быть принят детерминированным конечным автоматом DFA);

• it can be accepted by a nondeterministic finite state machine (он может быть принят недетерминированным конечным автоматом NFA);

• it can be accepted by an alternating finite automaton (он может быть принят альтернирующим конечным автоматом);

• it can be described by a formal regular expression. Note that the "regular expression" features provided with many programming languages are augmented with features that make them capable of recognizing languages which are not regular, and are therefore not strictly equivalent to formal regular expressions (он может быть описан с помощью формального регулярного выражения. Обратите внимание на то, что свойство «регулярное выражение» обеспечивается во многих языках программирования и усиливается свойствами, которые дают им возможность распознавать языки, которые не являются регулярными, и поэтому они не являются строго формальными регулярными выражениями);

• it can be generated by a regular grammar (он может генерироваться регулярной грамматикой);

• it can be generated by a prefix grammar (он может генерироваться префиксной грамматикой);

• it can be accepted by a read-only Turing machine (он может приниматься машиной Тьюринга, работающей в режиме только чтение);

• it can be defined in monadic second-order logic (он может быть определен в монадической логике второго порядка);

• it is recognized by some finitely generated monoid (он может распознаваться некоторыми конечными генерируемыми моноидами (полугруппа);

• it is the pre-image of a subset of a finite monoid under a homomorphism from the free monoid on its alphabet (он является прообразом подмножества конечных моноидов над гомоморфизмом (гомоморфным отображением) от свободных моноидов на его алфавите);

In computer science, a right regular grammar (also called right linear grammar) is a formal grammar (N, Σ, P, S) such that all the production rules in P are of one of the following forms:

1. A → a - where A is a non-terminal in N and a is a terminal in Σ

2. A → aB - where A and B are in N and a is in Σ

3. A → ε - where A is in N and ε denotes the empty string, i.e. the string of length 0.

In a left regular grammar (also called left linear grammar), all rules obey the forms

1. A → a - where A is a non-terminal in N and a is a terminal in Σ

2. A → Ba - where A and B are in N and a is in Σ

3. A → ε - where A is in N and ε is the empty string.

An example of a right regular grammar G with N = {S, A}, Σ = {a, b, c}, P consists of the following rules

S → aS

S → bA

A → ε

A → cA

and S is the start symbol. This grammar describes the same language as the regular expression a*bc*.

A regular grammar is a left regular or right regular grammar.

Some textbooks and articles disallow empty production rules, and assume that the empty string is not present in languages.

In computer science, a terminal value is a string or character representing the end. eg, a terminal value is introduced when one hits the 'enter' key in order to start a new paragraph.

Terminal value may also refer to a symbol of a grammar definition from Backus-Naur form. A terminal value in Bakus-Naur form is the name of a symbol that never appears on the left-hand side of the grammar list. For example: <top_node> ::= <node1> | <node2> <node1> ::= hello | goodbye <node2> ::= Dave | James

Here the symbols 'hello','goodbye','Dave' and 'James' are the terminal symbols, i.e. the bottom level of the grammar, what you actually see.

A prefix grammar G is a 3-tuple, (Σ, S, P), where

• Σ is a finite alphabet

• S is a finite set of base strings over Σ

• P is a set of production rules of the form u → v where u and v are strings over Σ

For strings x, y, we write x →_G y (and say: G can derive y from x in one step) if there are strings u, v, w such that x = vu, y = wu, and v → w is in P. Note that →_G is a binary relation on the strings of Σ.

The language of G, denoted L(G), is the set of strings derivable from S in zero or more steps: formally, the set of strings w such that for some s in S, s R w, where R is the transitive closure of →_G.

Turing machines are basic abstract symbol-manipulating devices which, despite their simplicity, can be adapted to simulate the logic of any computer algorithm. They were described in 1936 by Alan Turing. Turing machines are not intended as a practical computing technology, but a thought experiment about the limits of mechanical computation. Thus they were not actually constructed.

The Turing machine mathematically models a machine that mechanically operates on a tape on which symbols are written which it can read and write one at a time using a tape head. Operation is fully determined by a finite set of elementary instructions such as "in state 42, if the symbol seen is 0, write a 1; if the symbol seen is 1, shift to the right, and change into state 17; in state 17, if the symbol seen is 0, write a 1 and change to state 6;" etc. In the original article ("On computable numbers, with an application to the Entscheidungsproblem", see also references below), Turing imagines not a mechanical machine, but a person whom he calls the "computer", who executes these deterministic mechanical rules slavishly (or as Turing puts it, "in a desultory manner").

Monadic Second Order Logic

In mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic or infinitary logic. This formal system is distinguished from other systems in that its formulas contain variables which can be quantified. Two common quantifiers are the existential ∃ and universal ∀ quantifiers. The variables could be elements in the universe, or perhaps relations or functions over the universe. For instance, an existential quantifier over a function symbol would be interpreted as modifier "there is a function".

In informal usage, the term "predicate logic" occasionally refers to first-order logic. Some authors consider the predicate calculus to be an axiomatized form of predicate logic, and the predicate logic to be derived from an informal, more intuitive development.^[1]

First-order logic is a formal logic used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, and predicate logic. First-order logic is distinguished from propositional logic by its use of quantifiers; each interpretation of first-order logic includes a domain of discourse over which the quantifiers range.

A sentence in second-order logic, as in first-order logic, is a well-formed formula with no free variables (of any sort).

In monadic second-order logic, only variables for subsets of the domain are added. The second-order logic with all the sorts of variables just described is sometimes called full second-order logic to distinguish it from the monadic version.

Just as in first-order logic, second-order logic may include non-logical symbols in a particular second-order language. These are restricted, however, in that all terms that they form must be either first-order terms (which can be substituted for a first-order variable) or second-order terms (which can be substituted for a second-order variable of an appropriate sort).

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in a number of branches of mathematics and capture the idea of function composition; indeed, this notion is abstracted in category theory, where the monoid is a category with one object. Monoids are also commonly used to provide an algebraic foundation for computer science; in this case, the transition monoid and syntactic monoid are used in describing a finite state machine, whereas trace monoids and history monoids provide a foundation for process calculi and concurrent computing. Some of the more important results in the study of monoids are the Krohn-Rhodes theorem and the star height problem. The history of monoids, as well as a discussion of additional general properties, are found in the article on semigroups.

In mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them. This is used for groups and related concepts.

The term identity element is often shortened to identity when there is no possibility of confusion; we do so in this article.

Let (S,*) be a set S with a binary operation * on it (known as a magma). Then an element e of S is called a left identity if e * a = a for all a in S, and a right identity if a * e = a for all a in S. If e is both a left identity and a right identity, then it is called a two-sided identity, or simply an identity.

An identity with respect to addition is called an additive identity (often denoted as 0) and an identity with respect to multiplication is called a multiplicative identity (often denoted as 1). The distinction is used most often for sets that support both binary operations, such as rings. The multiplicative identity is often called the unit in the latter context, where, unfortunately, a unit is also sometimes used to mean an element with a multiplicative inverse.

In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures (such as groups, rings, or vector spaces). The word homomorphism comes from the Greek language: ὁμός (homos) meaning "same" and μορφή (morphe) meaning "shape".

DFAs are equivalent in computing power to nondeterministic finite automata.

On the other hand, Finite State Automata are of strictly limited power in the languages they can recognize — many simple languages, including any problem that requires more than constant space to solve, cannot be recognized by a DFA. The classical example of a simply described language that no DFA can recognize is bracket language, that is, language that consists of properly paired brackets, such as (()()). More formally the language consisting of strings of the form aⁿbⁿ — some finite number of a's, followed by an equal number of b's. If there is no limit to recursion (i.e., you can always embed another pair of brackets inside) it would require an infinite amount of states to recognize.

Автомат DFA по своим вычислительным возможностям эквивалентны недетерминированным конечным автоматам.

С другой стороны, конечные автоматы имеют строго ограниченные возможности в отношении языков, которые они распознают – множество простых языков, включая любые проблемы, требующие свыше определенного постоянного пространства для решения, не распознаются автоматом DFA. Классический пример языка с простым описанием, которые не распознается автоматом DFA, является скобочный язык, т.е. язык, который включает соответствующее количество парных скобок вида (()()). Более формально, язык, состоящий из строк вида aⁿbⁿ – некоторые конечные числа а, за которыми следуют равные числа b. Если при этом не имеется предела по рекурсии (т.е. когда Вы всегда можете вставлять другую пару скобок внутри), но это потребует распознавания бесконечного числа состояний.

In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. This distinguishes it from the deterministic finite automaton (DFA), where the next possible state is uniquely determined. Although the DFA and NFA have distinct definitions, it may be shown in the formal theory that they are equivalent, in that, for any given NFA, one may construct an equivalent DFA, and vice-versa: this is the powerset construction. Both types of automata recognize only regular languages. Non-deterministic finite state machines are sometimes studied by the name subshifts of finite type. Non-deterministic finite state machines are generalized by probabilistic automata, which assign a probability to each state transition.

В теории вычислений недетерминированные конечные автоматы NFA – это такие конечные автоматы, в которых для каждой пары состояний и входных символов может быть несколько возможных следующих состояний. Это отличает их от автоматов DFA, в которых следующее возможное состояние однозначно определено. Хотя автоматы DFA и NFA имеют отличные определения, можно при этом показать с точки зрения формальной теории их эквивалентность, например, для любой заданной NFA можно создать эквивалентную ей DFA и наоборот: это конструкция со степенным множеством. Оба типа автоматов распознают только регулярные языки.

Автоматы NFA иногда изучаются в разделе суб-сдвиги финитного типа. Понятия автоматы NFA обобщаются с помощью вероятностного автомата, который определяет вероятность каждого перехода.

In mathematics, subshifts of finite type are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics and ergodic theory. They also describe the set of all possible sequences executed by a finite state machine. The most widely studied shift spaces are the subshifts of finite type.