thompson_automaton (477B)
1 # Thompson automaton 2 3 construction to transform [regular_expression] to [automata_nondeterministic] with [epsilon_transition] 4 5 properties: 6 - [states] with an incoming character transition have exactly one [predecessor] 7 - almost a [series_parallel_graph], except for [kleene_star] 8 - almost a [DAG], except for [kleene_star]: 9 - any cycle-free path has at most one back-edge 10 11 Up: [conversion_automata] 12 13 See also: [glushkov_automaton] 14 15 Aliases: thompson's automaton, TNFA, TNFAs