1.
Finite-state machine
–
A finite-state machine or finite-state automaton, finite automaton, or simply a state machine, is a mathematical model of computation. It is a machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to external inputs. A FSM is defined by a list of its states, its state. The behavior of machines can be observed in many devices in modern society that perform a predetermined sequence of actions depending on a sequence of events with which they are presented. The finite state machine has less power than some other models of computation such as the Turing machine. The computational power distinction means there are tasks that a Turing machine can do. This is because a FSMs memory is limited by the number of states it has, FSMs are studied in the more general field of automata theory. An example of a mechanism that can be modeled by a machine is a turnstile. A turnstile, used to access to subways and amusement park rides, is a gate with three rotating arms at waist height, one across the entryway. Initially the arms are locked, blocking the entry, preventing patrons from passing through, depositing a coin or token in a slot on the turnstile unlocks the arms, allowing a single customer to push through. After the customer passes through, the arms are locked again until another coin is inserted, considered as a state machine, the turnstile has two possible states, Locked and Unlocked. There are two inputs that affect its state, putting a coin in the slot and pushing the arm. In the locked state, pushing on the arm has no effect, no matter how many times the input push is given, putting a coin in – that is, giving the machine a coin input – shifts the state from Locked to Unlocked. In the unlocked state, putting additional coins in has no effect, however, a customer pushing through the arms, giving a push input, shifts the state back to Locked. Each state is represented by a node, edges show the transitions from one state to another. Each arrow is labeled with the input that triggers that transition, an input that doesnt cause a change of state is represented by a circular arrow returning to the original state. The arrow into the Locked node from the dot indicates it is the initial state

2.
Regular language
–
Alternatively, a regular language can be defined as a language recognized by a finite automaton. The equivalence of regular expressions and finite automata is known as Kleenes theorem, in the Chomsky hierarchy, regular languages are defined to be the languages that are generated by Type-3 grammars. Regular languages are very useful in input parsing and programming language design, the collection of regular languages over an alphabet Σ is defined recursively as follows, The empty language Ø, and the empty string language are regular languages. For each a ∈ Σ, the language is a regular language. If A and B are regular languages, then A ∪ B, A • B, no other languages over Σ are regular. See regular expression for its syntax and semantics, note that the above cases are in effect the defining rules of regular expression. All finite languages are regular, in particular the empty string language = Ø* is regular, a simple example of a language that is not regular is the set of strings. Intuitively, it cannot be recognized with an automaton, since a finite automaton has finite memory. Techniques to prove this fact rigorously are given below, and 10. are purely algebraic approaches to define regular languages, a similar set of statements can be formulated for a monoid M⊂Σ*. In this case, equivalence over M leads to the concept of a recognizable language, some authors use one of the above properties different from 1. as alternative definition of regular languages. Some of the equivalences above, particularly those among the first four formalisms, are called Kleenes theorem in textbooks, precisely which one is called such varies between authors. One textbook calls the equivalence of regular expressions and NFAs Kleenes theorem, another textbook calls the equivalence of regular expressions and DFAs Kleenes theorem. Two other textbooks first prove the equivalence of NFAs and DFAs. Other authors simply define rational expression and regular expressions as synonymous and do the same with rational languages, the regular operations, K ∪ L, concatenation K ∘ L, and Kleene star L*. The trio operations, string homomorphism, inverse string homomorphism, as a consequence they are closed under arbitrary finite state transductions, like quotient K / L with a regular language. Even more, regular languages are closed under quotients with arbitrary languages, given two deterministic finite automata A and B, it is decidable whether they accept the same language. Disjointness, is LA ∩ LB =, membership, given a ∈ Σ*, is a ∈ LB. For regular expressions, the universality problem is NP-complete already for a singleton alphabet, for larger alphabets, that problem is PSPACE-complete

3.
Automata theory
–
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in computer science and discrete mathematics. The word automata comes from the Greek word αὐτόματα, which means self-acting, the figure at right illustrates a finite-state machine, which belongs to a well-known type of automaton. This automaton consists of states and transitions, as the automaton sees a symbol of input, it makes a transition to another state, according to its transition function, which takes the current state and the recent symbol as its inputs. Automata theory is related to formal language theory. An automaton is a representation of a formal language that may be an infinite set. Automata play a role in theory of computation, compiler construction, artificial intelligence, parsing. Following is a definition of one type of automaton, which attempts to help one grasp the essential concepts involved in automata theory/theories. An automaton is supposed to run on some given sequence of inputs in time steps. An automaton gets one input every step that is picked up from a set of symbols or letters. At any time, the symbols so far fed to the automaton as input, form a sequence of symbols. An automaton contains a set of states. At each instance in time of run, the automaton is in one of its states. At each time step when the automaton reads a symbol, it jumps or transitions to state that is decided by a function that takes the current state. This function is called the transition function, the automaton reads the symbols of the input word one after another and transitions from state to state according to the transition function, until the word is read completely. Once the input word has been read, the automaton is said to have stopped, depending on the final state, its said that the automaton either accepts or rejects an input word. There is a subset of states of the automaton, which is defined as the set of accepting states, if the final state is an accepting state, then the automaton accepts the word. The set of all the words accepted by an automaton is called the language of that automaton, any subset of the language of an automaton is a language recognized by that automaton

4.
Synchronizing word
–
Not every DFA has a synchronizing word, for instance, a DFA with two states, one for words of even length and one for words of odd length, can never be synchronized. Given a DFA, the problem of determining if it has a word can be solved in polynomial time using a theorem due to Černý. A simple approach considers the set of states of the DFA, and builds a directed graph where nodes belong to the power set. A path from in the graph to a singleton state shows the existence of a synchronizing word and this algorithm is exponential in the number of states. The problem of estimating the length of synchronizing words has a history and was posed independently by several authors. In 1964 Jan Černý conjectured that 2 is the bound for the length of the shortest synchronizing word for any n-state complete DFA. If this is true, it would be tight, in his 1964 paper, the best upper bound known is /6, far from the lower bound. For n-state DFAs over a k-letter input alphabet, an algorithm by David Eppstein finds a word of length at most 11n3/48 + O. This algorithm does not always find the shortest possible synchronizing word for an automaton, as Eppstein also shows. The road coloring problem is the problem of labeling the edges of a directed graph with the symbols of a k-letter input alphabet in order to form a synchronizable DFA. A transformation semigroup is synchronizing if it contains an element of rank 1, a DFA corresponds to a transformation semigroup with a distinguished generator set. Černýs conjecture, retrospects and prospects, Proc, volkov, Mikhail V. Synchronizing Automata and the Černý Conjecture, Proc. Language and Automata Theory and Applications, LNCS,5196, Springer-Verlag, pp. 11–27

5.
Avraham Trahtman
–
Avraham Naumovich Trahtman is a mathematician at Bar-Ilan University. In 2007, Trahtman solved a problem in combinatorics that had been open for 37 years, trahtmans solution to the road coloring problem was accepted in 2007 and published in 2009 by the Israel Journal of Mathematics. The problem arose in the subfield of symbolic dynamics, a part of the field of dynamical systems. The road coloring problem was raised by R. L. Adler and L. W. Goodwyn from the United States, the proof used results from earlier work. The problem of estimating the length of synchronizing word has a history and was posed independently by several authors. In 1964 Jan Černý conjectured that 2 is the bound for the length of the shortest synchronizing word for any n-state complete DFA. If this is true, it would be tight, in his 1964 paper, in 2011 Trakhtman published a proof of upper bound n/48, but then he found an error in it. The conjecture holds in many cases, see for instance, Kari. The finite basis problem for semigroups of order less than six in the theory of semigroups was posed by Alfred Tarski in 1966, in 1983, Trahtman solved this problem by proving that all semigroups of order less than six are finitely based. In the theory of varieties of semigroups and universal algebras the problem of existence of covering elements in the lattice of varieties was posed by Evans in 1971, the positive solution of the problem was found by Trahtman. He also found a six-element semigroup that generates a variety with a continuum of subvarieties, the theory of locally testable automata can be based on the theory of varieties of locally testable semigroups. Trahtman found the precise estimation on the order of local testability of finite automata, there are results in theoretical mechanics and in the promising area of extracting moisture from the air mentioned in New Scientist