|
Counter-free Language
An aperiodic finite-state automaton (also called a counter-free automaton) is a finite-state automaton whose transition monoid is aperiodic. Properties A regular language is star-free if and only if it is accepted by an automaton with a finite and aperiodic transition monoid. This result of algebraic automata theory is due to Marcel-Paul Schützenberger. In particular, the minimum automaton of a star-free language is always counter-free (however, a star-free language may also be recognized by other automata which are not aperiodic). A counter-free language is a regular language for which there is an integer ''n'' such that for all words ''x'', ''y'', ''z'' and integers ''m'' ≥ ''n'' we have ''xy''''m''''z'' in ''L'' if and only if ''xy''''n''''z'' in ''L''. Another way to state Schützenberger's theorem is that star-free languages and counter-free languages are the same thing. An aperiodic automaton satisfies the Černý conjecture. References * * — An intensive exa ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Finite-state Automaton
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract 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 some inputs; the change from one state to another is called a ''transition''. An FSM is defined by a list of its states, its initial state, and the inputs that trigger each transition. Finite-state machines are of two types— deterministic finite-state machines and non-deterministic finite-state machines. A deterministic finite-state machine can be constructed equivalent to any non-deterministic one. The behavior of state 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. Simple examples are vending machines, which dispense pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Transition Monoid
In mathematics and theoretical computer science, a semiautomaton is a deterministic finite automaton having inputs but no output. It consists of a set ''Q'' of states, a set Σ called the input alphabet, and a function ''T'': ''Q'' × Σ → ''Q'' called the transition function. Associated with any semiautomaton is a monoid called the characteristic monoid, input monoid, transition monoid or transition system of the semiautomaton, which acts on the set of states ''Q''. This may be viewed either as an action of the free monoid of strings in the input alphabet Σ, or as the induced transformation semigroup of ''Q''. In older books like Clifford and Preston (1967) semigroup actions are called "operands". In category theory, semiautomata essentially are functors. Transformation semigroups and monoid acts : A transformation semigroup or transformation monoid is a pair (M,Q) consisting of a set ''Q'' (often called the "set of states") and a semigroup or monoid ''M'' of funct ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Aperiodic Monoid
In mathematics, an aperiodic semigroup is a semigroup ''S'' such that every element ''x'' ∈ ''S'' is aperiodic, that is, for each ''x'' there exists a positive integer ''n'' such that ''x''''n'' = ''x''''n'' + 1. An aperiodic monoid is an aperiodic semigroup which is a monoid. Finite aperiodic semigroups A finite semigroup is aperiodic if and only if it contains no nontrivial subgroups, so a synonym used (only?) in such contexts is group-free semigroup. In terms of Green's relations, a finite semigroup is aperiodic if and only if its ''H''-relation is trivial. These two characterizations extend to group-bound semigroups. A celebrated result of algebraic automata theory due to Marcel-Paul Schützenberger asserts that a language is star-free if and only if its syntactic monoid is finite and aperiodic.Schützenberger, Marcel-Paul, "On finite monoids having only trivial subgroups," ''Information and Control'', Vol 8 No. 2, pp. 190–194, 1965. A consequence of the Krohn–Rhode ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Regular Language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to many modern regular expressions engines, which are augmented with features that allow recognition of non-regular languages). 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 Kleene's theorem (after American mathematician Stephen Cole Kleene). In the Chomsky hierarchy, regular languages are the languages generated by Type-3 grammars. Formal definition The collection of regular languages over an alphabet Σ is defined recursively as follows: * The empty language Ø is a regular language. * For each ''a'' ∈ Σ (''a'' belongs to Σ), the singleton language is a regular language. * If ''A'' is a regular language, ''A'' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Star-free Language
A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star.Lawson (2004) p.235 For instance, the language of words over the alphabet \ that do not have consecutive a's can be defined by (\emptyset^c aa \emptyset^c)^c, where X^c denotes the complement of a subset X of \^*. The condition is equivalent to having generalized star height zero. An example of a regular language which is not star-free is \, i.e. the language of strings consisting of an even number of "a". Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids.Lawson (2004) p.262 They can also be characterized logically as languages definable in FO the first-order logic over the natural numbers with the less-than relation, as the counter-free languages and as languages def ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton (automata in plural) is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton (FA) or Finite-State Machine (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of states (represented in the figure by circles) and transitions (represented by arrows). As the automaton sees a symbol of input, it makes a transition (or jump) to another state, according to its transition function, which takes the previous state and current input symbol as its arguments. Automata the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Marcel-Paul Schützenberger
Marcel-Paul "Marco" Schützenberger (24 October 1920 – 29 July 1996) was a French mathematician and Doctor of Medicine. He worked in the fields of formal language, combinatorics, and information theory.Herbert Wilf, Dominique Foata, ''et al.'',In Memoriam: Marcel-Paul Schützenberger, 1920-1996," ''Electronic Journal of Combinatorics'', served from University of Pennsylvania Dept. of Mathematics Server, article dated 12 October 1996, retrieved from WWW on 4 November 2006. In addition to his formal results in mathematics, he was "deeply involved in struggle against the votaries of eo-arwinism",Foata, Dominique, "In Memoriam," ''op. cit.'' a stance which has resulted in some mixed reactions from his peers and from critics of his stance on evolution. Several notable theorems and objects in mathematics as well as computer science bear his name (for example Schutzenberger group or the Chomsky–Schützenberger hierarchy). Paul Schützenberger was his great-grandfather. In the l ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
DFA Minimization
In automata theory (a branch of theoretical computer science), DFA minimization is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equivalent if they recognize the same regular language. Several different algorithms accomplishing this task are known and described in standard textbooks on automata theory. Minimal DFA For each regular language, there also exists a minimal automaton that accepts it, that is, a DFA with a minimum number of states and this DFA is unique (except that states can be given different names). The minimal DFA ensures minimal computational cost for tasks such as pattern matching. There are two classes of states that can be removed or merged from the original DFA without affecting the language it accepts. * Unreachable states are the states that are not reachable from the initial state of the DFA, for any input string. These states can be removed. * D ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Černý Conjecture
In computer science, more precisely, in the theory of deterministic finite automata (DFA), a synchronizing word or reset sequence is a word in the input alphabet of the DFA that sends any state of the DFA to one and the same state.Avraham Trakhtman''Synchronizing automata, algorithms, Cerny Conjecture'' Accessed May 15, 2010. That is, if an ensemble of copies of the DFA are each started in different states, and all of the copies process the synchronizing word, they will all end up in the same state. 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. Existence Given a DFA, the problem of determining if it has a synchronizing word can be solved in polynomial time using a theorem due to Ján Černý. A simple approach considers the power set of states of the DFA, and builds a directed graph where nodes belong to the power set, and a directed edge describes the action of t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Green's Relations
In mathematics, Green's relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. The relations are named for James Alexander Green, who introduced them in a paper of 1951. John Mackintosh Howie, a prominent semigroup theorist, described this work as "so all-pervading that, on encountering a new semigroup, almost the first question one asks is 'What are the Green relations like?'" (Howie 2002). The relations are useful for understanding the nature of divisibility in a semigroup; they are also valid for groups, but in this case tell us nothing useful, because groups always have divisibility. Instead of working directly with a semigroup ''S'', it is convenient to define Green's relations over the monoid ''S''1. (''S''1 is "''S'' with an identity adjoined if necessary"; if ''S'' is not already a monoid, a new element is adjoined and defined to be an identity.) This ensures that principal ideals generated by ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
