Skip to content
Hallway
0:00 / 0:00

#dfa#regularexpressions#brzozowskiderivatives

Fun and games generating DFAs from regular expressions

Kay Lack

49K subscribers • 3 videos on Hallway

YouTube
  • Recommended by 1 person: 1 in engineering communities.
  • Presented by Kay Lack

Intermediate. Assumes working knowledge.

9.7K views1 year ago1 recommendation

Computer scienceProgramming languagesCompilers and interpretersAlgorithmsComputation and complexity

Kay Lack explains various algorithms for generating deterministic finite automata from regular expressions, including Brzozowski derivatives and subset construction.

This video has a page on 0DE5 with exercises and resources 0de5.net/stimuli/fun-and-games-generating-dfas-from-regular-… Chapters - Intro - Power/subset construction - Regex history - McNaughton & Yamada's algorithm - Brzozowski derivatives - Regex history 2 - Aho's Followpos algorithm - Epilogue

Why it's here

1 person recommends this

What people say. Recommended as a helpful resource for understanding Brzozowski derivatives and DFA generation.

u/Aaron1924in r/rust • Recommends

On “rzozowski: a Brzozowski derivative-based regex crate for the real world”

Oh nice, I've seen a youtube video about this recently and was thinking about implementing this myself **One nitpick:** It looks like you're treating the regex as an immutable data structure which you keep rebuilding instead of modifying it in-place. You might want to consider using `Arc<Regex>` instead of `Box<Regex>` for your tree structure so you don't have to deep-copy everything all the time.
10View on Reddit