wiki_research

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

automata_determinization (457B)

      1 # Automata determinization
      2 
      3 [Conversion] of [NFA] into [DFA]
      4 
      5 Usual construction: [powerset_automata]
      6 
      7 The bound on [state_complexity] is exactly 2^n: some [NFAs] on a binary alphabet have n [automaton_states] and their [canonical_DFA] (as a [complete_automaton]) has exactly 2^n [automaton_states]
      8 - [meyer1971economy]
      9 - [moore1971bounds]
     10 
     11 Bounds for specific [automata_classes]:
     12 - [unary_ufa]
     13 
     14 Up: [automata_constructions]
     15 
     16 Aliases: automata determinized