wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

glushkov_automaton (581B)

      1 # Glushkov automaton
      2 
      3 https://en.wikipedia.org/wiki/Glushkov%27s_construction_algorithm
      4 
      5 The *Glushkov automaton* is an [NFA] constructed from a [regular_expression] which recognizes the same language
      6 
      7 It is a [homogeneous_automaton]
      8 
      9 [glushkov_automaton_construction]
     10 
     11 It has O(m^2) transitions with m the [regular_expression], according to [allauzen2006unified] or [nicaud2009average]
     12 
     13 Unlike [thompson_automaton], it does not contain [epsilon_transitions]
     14 
     15 Connections to [local_languages]
     16 
     17 Up: [conversion_automata]
     18 
     19 See also: [thompson_automaton]
     20 
     21 Aliases: position automaton