page_title: Induction of regular languages
section_title: Successor automata
hierarchical_section_title: Induction of regular languages / Approaches / Successor automata
caption_attribution_description: Deutsch: Schemazeichnung zur Verdeutlichung des Pumping-Lemmas, eines Satzes der theoretischen Informatik. English: Demonstration of the pumping lemma for regular languages: Whenever a finite automaton A with n states recognizes a word uvw (shown: starting from an initial state q1, A reaches an accepting state qm on input uvw) of more than n characters, A must reach some state twice (shown: qs = qt). Hence when the middle part v is repeated ("pumped") arbitrarily often (e.g. uvvw, uvvvw, ...), the word is still recognized.
context_page_description: In computational learning theory, induction of regular languages refers to the task of learning a formal description of a regular language from a given set of example strings. Although Mark E. Gold has shown that not every regular language can be learned this way, approaches have been investigated for a variety of subclasses. They are sketched in this article.
context_section_description: From a given set of input strings, Vernadat and Richetin build a so-called successor automaton, consisting of one state for each distinct character and a transition between each two adjacent characters' states.
  For example, the singleton input set { aabbaabb } leads to an automaton corresponding to the regular expression (a⁺⋅b⁺)*.
  An extension of this approach is the predecessor-successor method which generalizes each character repetition immediately to a Kleene ⁺ and then includes for each character the set of its possible predecessors in its state.
  Successor automata can learn exactly the class of local languages.
  Since each regular language is the homomorphic image of a local language, grammars from the former class can be learned by lifting, if an appropriate (depending on the intended application) homomorphism is provided.
  In particular, there is such a homomorphism for the class of languages learnable by the predecessor-successor method.
  The learnability of local languages can be reduced to that of k-reversible languages.
caption: Illustration of the pumping lemma for regular automata
exif: {}