Brzozowski Derivatives (aka WTF is a regex derivative?!)

An explanation of Brzozowski derivatives, showing how to compute the derivative of a regular expression and use it for string matching.

Here we introduce the idea of a "derivative" of a regular expression (regex). The idea is to "divide" out the string that you're using out of the strings that are generated by the regex. We give a definition of what a derivative of a language is, and prove that the properties hold when considering a regex. The purpose of these derivatives (called "Brzozowski Derivatives") is that one can determine whether or not a regex can generate a string by repeatedly applying a derivative to each character of the string. Contribute: Paypal: paypal.me/easytheory Patreon: patreon.com/easytheory Discord: discord.gg/SD4U3hs Live Streaming (Sundays 2PM GMT, 2 hours): Twitch: twitch.tv/easytheory (Youtube also) Merch: Language Hierarchy Apparel: teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmatio… Gold Supporters: Micah Wood Silver Supporters: Timmy Gy ▶ADDITIONAL QUESTIONS◀ 1. What if we permitted additional operations for regexes, such as complement or intersection? ▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.