Conversion of Regex to DFA Directly with Brzozowski Derivatives

Here we show, with an example, that one can create a DFA directly from a regular expression using Brzozowski Derivatives. Therefore, no NFA is ever needed to do the conversion. We first set the start state to be the original regex, and its transitions correspond to taking partial derivatives of that regex with each of the input characters. If a new regex is formed that hasn't been seen before, then that transition goes to a new state. This is repeated until no new states are formed, and the final states are ones that can make the empty string (epsilon).

#easytheory #gate #theory

Contribute:

Youtube Live Streaming (Sundays) - subscribe for when these occur.

Social Media:

Merch:

Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy

▶SEND ME THEORY QUESTIONS◀

▶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.

[yazidkhaldi]

After watching the video titled "Cloudflare Deploys Really Slow Code, Takes Down Internet, " it reminded me of the last time I encountered DFA and NFA concepts, which was approximately five years ago during a compiler design course. Now, I'm here to refresh my memory on these topics.

[Squirroo]

Thank you so much for this video! This made it much more clear than my textbook did :)

[liam]

Ty man! i appreciate it so much, i love the content

[waynee]

From the description: " its transitions correspond to taking partial derivatives of that regex with each of the input characters".
Partial derivative here is meant as "taking the derivative with each character in the input alphabet" right?

Because interestingly the term "partial derivative" was defined in a paper by Antimirov in 1995 called "Partial derivatives of regular expressions and finite automaton constructions". In that paper he introduces the "partial derivative" compared to the "Brzozowski derivative" and shows that partial derivatives relate naturally to NFAs the same Brzozowski derivatives relate to DFAs.