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

[@wayfaringstranger579]

thank you so much for making this video!! I don't know how I would pass my discrete maths course without you

[@EasyTheory]

You're welcome :)

[@waynee95]

It's a really cool topic. Cool that you covered it. Not sure if you will cover the "Brzozowski construction" which uses the derivative approach to construct a DFA from a RE. Which will also work for REs containing complement and intersection operations. Which does not work with the traditional route using RE -> NFA -> DFA.

[@EasyTheory]

Guess what's coming on Friday ;)

[@waynee95]

@@EasyTheory Nice!

[@selinamartinez8067]

Just like what you said about when a = b in no.3, I thought that there should be a set only with the empty string in it when a = b in no.1 But it was always empty set. and you said epsilon is not a single character. I thought it is.. I thought that a single character and a single string is the same thing... Then.. is the string a thing consist of each characters?? and empty string is a only exceptation that only can be a string without a character??

[@selinamartinez8067]

Always thank you for your videos!!!

[@robharwood3538]

You can think of a string as a list of characters, including the possibility that the list of characters is empty. In other words, a list has a 'length', i.e. the number of elements in the list (in this case, the 'elements' are characters); and the length of the list can be any non-negative number, *including* 0. For example, if we use double-quotes to denote the beginning and ending of a string, then "this-is-an-example-string" is a string (a list of characters), and its length is 25 (it contains 25 characters). A string that contains a single character might be "c", a list containing only a single element, the character c, and so this string has a length of 1. And the empty string would simply be two double-quotes with nothing in between, namely "", which is a string of length 0. So, you can think of ε as being in some sense equivalent to "". So ε isn't a character itself. It's a string of length 0! If it helps with understanding, then, you can also think of 'characters' as strings of length 1. E.g. the character c could be written as "c", which is a string (list of characters) of length 1, containing only one character, namely the character c. In this way, you can think of the transitions in an NFA as always being strings, but only strings of length 0 (ε), or of length 1 (a single character). The case of the empty set ∅ -- as opposed to the empty string ε -- can be thought of as 'no string at all!', or 'not even the empty string!', i.e. not even a list (of characters) at all. In a programming language, this is often denoted as a variable with a value of 'null'. So, if we think of a variable t (for 'transition'), then there are three possibilities: 1. t = null, there is no string at all. This corresponds to the empty set ∅. 2. t = "", the empty string (the string of length 0). This is ε. 3. t = "c", a string with a single character (a string of length 1), where 'c' can be any single character. This corresponds to the usual transitions in a DFA, where every transition must use up exactly one character.

[@abdelbassetomiri530]

thanks a lot for the video prof extremely helpful can you please explain how one generates the regex's DFA using this method, please.

[@agnishom]

Thanks for doing this video!

[@EasyTheory]

You're welcome!

[@tricky778]

why do you use the "raised to the power of minus one" notation?

[@EasyTheory]

Unfortunately it's because that's what most people use when referring to regex derivatives. I hate the notation too, but the "partial derivative" notation with respect to some string is somewhat cumbersome to write over and over.

[@tricky778]

@@EasyTheory oh, it's really supposed to be the reciprocal of the prefix? (uv)(u^-1) = v ? strings are defined such that they're a non-abelian group where the product operator is concatenation, not the additive operator ?

[@EasyTheory]

@@tricky778 You can think of it that way, yes. But when defined for a language, say u^(-1) L, then it's just the name of the language and doesn't actually mean anything else.

[@josejaviermoya-angelergarc6968]

great video!🙂

[@ssjng]

helped me a lot!!

[@PatríciaPalmiradeSousa]

thank you so much, i´m portuguese, but your explanation was excellent

[@vimalathithand917]

A cool topic

[@samjudelson]

Thanks!

[@victorvalenciasanchez6756]

thanks a lot dude