Remorhaz\UniLex\RegExp\FSM\DfaBuilder::fromNfa()

Complexity

Conditions	27
Paths	> 20000

Size

Total Lines	141
Code Lines	91

Duplication

Lines	0
Ratio	0 %

Importance

Changes

0

<?php
    public static function fromNfa(Nfa $nfa): Dfa
    {
        $dfa = new Dfa();
        (new self($dfa, $nfa))->run();

        $stateQuery = [];
        $nonEquivalentStates = [];
        $dfaStates = $dfa->getStateMap()->getStateList();
        $devilState = max($dfaStates) + 1;
        $dfaStates[] = $devilState;

        $transitionMap = [];

        foreach ($dfaStates as $stateA) {
            foreach ($dfaStates as $stateB) {
                $marked = $nonEquivalentStates[$stateA][$stateB] ?? false;
                if ($marked) {
                    continue;
                }
                $isFinishStateA = $stateA == $devilState
                    ? false
                    : $dfa->getStateMap()->isFinishState($stateA);
                $isFinishStateB = $stateB == $devilState
                    ? false
                    : $dfa->getStateMap()->isFinishState($stateB);
                if ($isFinishStateA == $isFinishStateB) {
                    continue;
                }
                $nonEquivalentStates[$stateA][$stateB] = true;
                $nonEquivalentStates[$stateB][$stateA] = true;
                $stateQuery[] = [$stateA, $stateB];
            }
            $transitionMap[$stateA][$devilState] = $dfa->getSymbolTable()->getSymbolList();
        }

        // Making all finish states non-equivalent to distinguish regular expressions
        /*foreach ($dfa->getStateMap()->getFinishStateList() as $stateA) {
            foreach ($dfa->getStateMap()->getFinishStateList() as $stateB) {
                $marked = $nonEquivalentStates[$stateA][$stateB] ?? false;
                if ($marked) {
                    continue;
                }
                $nonEquivalentStates[$stateA][$stateB] = true;
                $nonEquivalentStates[$stateB][$stateA] = true;
                $stateQuery[] = [$stateA, $stateB];
            }
        }*/

        foreach ($dfa->getTransitionMap()->getTransitionList() as $sourceState => $transitions) {
            $devilStateSymbols = $dfa->getSymbolTable()->getSymbolList();
            foreach ($transitions as $targetState => $symbols) {
                $devilStateSymbols = array_diff($devilStateSymbols, $symbols);
                $transitionMap[$sourceState][$targetState] = $symbols;
            }
            $transitionMap[$sourceState][$devilState] = $devilStateSymbols;
        }

        while (!empty($stateQuery)) {
            [$firstTargetState, $secondTargetState] = array_pop($stateQuery);

            foreach ($dfaStates as $stateA) {
                foreach ($dfaStates as $stateB) {
                    $isMarked = $nonEquivalentStates[$stateA][$stateB] ?? false;
                    if ($isMarked) {
                        continue;
                    }
                    $symbolsA = $transitionMap[$stateA][$firstTargetState] ?? [];
                    $symbolsB = $transitionMap[$stateB][$secondTargetState] ?? [];
                    $symbols = array_intersect($symbolsA, $symbolsB);
                    if (!empty($symbols)) {
                        $nonEquivalentStates[$stateA][$stateB] = true;
                        $nonEquivalentStates[$stateB][$stateA] = true;
                        $stateQuery[] = [$stateA, $stateB];
                    }
                }
            }
        }

        $equivalentStates = [];
        $nextClass = 1;
        $classes = [];
        foreach ($dfaStates as $stateA) {
            if (!isset($classes[$stateA])) {
                $class = $nextClass++;
                foreach ($dfaStates as $stateB) {
                    $isMarked = $nonEquivalentStates[$stateA][$stateB] ?? false;
                    if (!$isMarked) {
                        $classes[$stateB] = $class;
                        if ($stateB != $devilState) {
                            $equivalentStates[$class][$stateB] = true;
                        }
                    }
                }
            }
        }

        $minimizedDfa = new Dfa();
        $minimizedDfa->setSymbolTable($dfa->getSymbolTable());
        $nfaStartStates = $nfa->getStateMap()->getStartStateList();
        $nfaFinishStates = $nfa->getStateMap()->getFinishStateList();
        $newDfaStates = [];
        foreach ($equivalentStates as $newState => $dfaStates) {
            $newValue = [];
            foreach (array_keys($dfaStates) as $dfaState) {
                $nfaStates = $dfa->getStateMap()->getStateValue($dfaState);
                $newValue = array_merge($newValue, $nfaStates);
                $newDfaStates[$dfaState] = $newState;
            }
            $newValue = array_unique($newValue);
            sort($newValue);
            $minimizedDfa->getStateMap()->createState($newValue);
            $isStartState = !empty(array_intersect($nfaStartStates, $newValue));
            if ($isStartState) {
                $minimizedDfa->getStateMap()->addStartState($newState);
            }
            $isFinishState = !empty(array_intersect($nfaFinishStates, $newValue));
            if ($isFinishState) {
                $minimizedDfa->getStateMap()->addFinishState($newState);
            }
        }
        $transitionMap = [];
        foreach ($dfa->getTransitionMap()->getTransitionList() as $sourceState => $transitions) {
            foreach ($transitions as $targetState => $symbols) {
                $newSourceState = $newDfaStates[$sourceState];
                $newTargetState = $newDfaStates[$targetState];
                $transitionMap[$newSourceState][$newTargetState] = array_unique(
                    array_merge(
                        $transitionMap[$newSourceState][$newTargetState] ?? [],
                        $symbols
                    )
                );
            }
        }
        foreach ($transitionMap as $sourceState => $transitions) {
            foreach ($transitions as $targetState => $symbols) {
                sort($symbols);
                $minimizedDfa->getTransitionMap()->addTransition($sourceState, $targetState, $symbols);
            }
        }

        return $minimizedDfa;
    }