Class: LexerKit::DFA::DFAMinimizer

Inherits:
Object
  • Object
show all
Defined in:
lib/lexer_kit/dfa/dfa_minimizer.rb

Overview

DFAMinimizer reduces DFA state count using Hopcroft’s algorithm. Merges equivalent states while preserving language recognition.

Instance Method Summary collapse

Constructor Details

#initialize(state_count:, transitions:, accept_states:, class_count:) ⇒ DFAMinimizer

Returns a new instance of DFAMinimizer.

Parameters:

  • state_count (Integer) —

    number of states (including dead state 0)

  • transitions (Array<Integer>) —

    state × class_count → next_state

  • accept_states (Hash<Integer, Integer>) —

    state → token_id

  • class_count (Integer) —

    number of byte classes



12
13
14
15
16
17
 
# File 'lib/lexer_kit/dfa/dfa_minimizer.rb', line 12

def initialize(state_count:, transitions:, accept_states:, class_count:)
  @state_count = state_count
  @transitions = transitions
  @accept_states = accept_states
  @class_count = class_count
end

Instance Method Details

#minimize ⇒ Hash

Minimize the DFA

Returns:

  • (Hash) —

    { state_count:, transitions:, accept_states: }



21
22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/lexer_kit/dfa/dfa_minimizer.rb', line 21

def minimize
  return trivial_result if @state_count <= 2

  # 1. Initial partition: group by acceptance status and token_id
  partitions = build_initial_partitions

  # 2. Refine partitions using Hopcroft's algorithm
  partitions = refine_partitions(partitions)

  # 3. Build minimized DFA
  build_minimized_dfa(partitions)
end