The way in which Prof Altenkirsch talks during this video is almost indistinguishable from the conversation a lone programmer would have with himself out loud during an intense programming session. If anyone ever wondered what programmers sound like when there's no-one to hear them code, this is pretty much it.
I work very closely with a developer doing custom dev for our ERP system. When we are sitting in a conference room going over bug tickets, he speaks quietly to himself most of the time as he works on the code. Then, he will ask a question somewhat louder and sometimes it seems like he might be asking me but I know at this point he almost never is. :)
So this is not an explanation of Regular Expressions as a tool, that we might use on a daily basis. This is the theoretical basis for how REs is implemented. It's stuff covered in undergrad CS, and one of the next lessons is making your own parser for your own programming language.
Right back to it, I see! There's an error in the example with the alternating as and bs at 0:59. It should not have a "+" (meaning or) in between "(ab)*" and "(a+ε)"
Sure seems like a nice, verysmart guy. I too watch purely for the fun of (almost~certainly) knowing that if you understand the arcane _jargon_ he is speaking then the _concepts_ are surely simply simple. LSS: Dude... you had me at "Non-Deterministic Automata"
It would have saved me a lot of time if the mystery regex had been shown correctly on the screen and the paper (from 20:38). The correct regex (with sensible symbols) is /(0|11|10(00|1)*01)*/. After I had wasted much time on the incorrect one, I drew the AST from the python code in a notebook since I didn't trust the comment above it. The comment was correct as it turned out. Here's the first matches: 0 : 0 11 : 3 (11) 110 : 6 (11 0) 1001 : 9 (10 01) 1100 : 12 (11 0 0) 1111 : 15 (11 11) 10010 : 18 (10 01 0) 10101 : 21 (10 1 01) 11000 : 24 (11 0 0 0) 11011 : 27 (11 0 11) 11110 : 30 (11 11 0) I think I can see the pattern.
The extra credit question on my DFA exam in college was "write a DFA that can determine If a binary number is divisible by 3. Hint, it has 3 states." I recognized the regex instantly.
@@babyeatingpsychopath Technically, shouldn't there be 4 states? The empty string is not "a binary number is divisible by 3", but it *is* your start state. Then you have 3 states for the 3 remainders modulo 3.
@@jursamaj technically, I believe you're correct, I suspect the actual instructions specified a nonzero length binary string. It's been a couple of decades since that exam.
I've always focused on just getting the re to serve some purpose. That's why I got an engineering degree, not a mathematics degree. But this helps me appreciate just how much math is under the hood (bonnet?)! It's fun listening to prof Altenkirsh even though the machine code episode was more my speed
What makes this project particular to "Python" Regular Expressions? Cause re exists and you could roll your own regex in most languages. Aren't you just making regexes (in some language, that happens to be python)?
Please change the title of this video. Python is not the important part. People are going to search for help with using regular expressions in Python (import re) and find this video which is not going to help.
@@BaronFirespawn Someone who doesn't know computerphile would only see a search result for a popular channel. Regardless, the "Python" in this video had nothing to do with the concept being shown.
He's implementing regex in terms of an NFA network, in code. He wrote python code for running any NFA network in a previous video. That code will also work on the regex-specific NFA networks he's constructing in this video. He chose Python because it had to be in some programming language, and Python is easier to write than in C for example. Edit: but yeah as others have said, the title of this video suggests it's about python's re regex library, or just regex in general, which could confuse viewers :/
This is the university experience. Just throw in you doing a homework assignment for this now, then studying for the exam on it. Somehow by the end you'll look back and realize you absorbed some amount of it because you know more than before you began.
Unit testing should also know the expected result. There should be some instant feedback instead of someone checking and saying, "Yep, that test case must return false, so it's okay".
Yeah... this definitely falls short of proper unit testing. Perhaps Prof. Altenkirch needs to learn to behave... or rather, to learn _behave_ -- the python implementation of the Cucumber conception of unit testing. :)
Prof Altenkirsch is definitely the Alien played by Jemaine Clement in Men in Black. It's so obvious he's a Supermax-escapee from the other side of the moon bent on taking over the world.
@@Imperial_Squid well, the title of that window (e.g. at 3:25) says "IPython Console"... you'll also see that sort of output in Jupyter Notebooks... I think a lot of these things are interconnected in some manner, though I don't know the details.
Why care about the POSIX or IETF standard syntaxes for Regular Expressions when you can just make up your own. For anybody finding this video and wanting to learn regular expressions, go watch a different video. This is a video about automata on the example of pattern matching and has basically nothing to do with regular expressions at all.
@@XenoTravis it's like a cross between BBC Basic from the 1980s and JavaScript, without any curly braces. And 'elif' - seriously? That just looks like a typo. Deep and shallow copies? Grrrr! Probably all straight forward if you start out learning to code in Python but really annoying if you are previously familiar with other languages. But the libraries are useful. Oh and why is there a while but not a do ... while ?
@@RedHair651 haven't thought about what I would do to improve it tbh. Sometimes it seems a little bit bare and I have to assume a lot of things. I would change the for loop or at least add in the classic c syntax along with their style. But that is just me being so used to the 'normal' way
The syntax is what you hate? There are way better reasons to hate Python: Mutability. Lack of a type system. Incorrectly / inconsistently-implemented scoping.
@@DrGreenGiant very much agreed. I wish more was done to draw attention to that distinction, though -- not to mention the fact that he's using a completely different syntax for his regular expressions than anything that's common in the UNIX [and similar] landscape... It's useful stuff if you're thinking about the abstract ideas of it all, but quite disconnected from practical everyday usage of existing implementations. 😕
@@DavidLindes Syntax isn't interesting. It's just arbitrary convention. The fundamental ideas are what matters ... the rest is just implementation details.
@@halfsourlizard9319 Syntax may not be "interesting" to the theory, but it's critically important to actually doing anything useful with actual computers. Also, it can be _very_ interesting -- see the IOCCC.
@@DavidLindes Knowing the theory behind regexps is the interesting bit; there are references (or LLMs) for the derpy idiosyncrasies of the various flavours.
It never came to me that the highest level of Pythonic is to lean back 40 degrees with your upper body while writing Python.
I do this too. Well, specifically I alternate between ultimate recline and ultimate shrimp lol
I find to be curled up in a fetal position to be most pythonic
Don't overlook the flower shirt, which is part of the proposed PEP9 spec.
@@kylek29 That trumps proper whitespaces.
@@DrGreenGiantI feel so seen right now 😂
The way in which Prof Altenkirsch talks during this video is almost indistinguishable from the conversation a lone programmer would have with himself out loud during an intense programming session. If anyone ever wondered what programmers sound like when there's no-one to hear them code, this is pretty much it.
I work very closely with a developer doing custom dev for our ERP system. When we are sitting in a conference room going over bug tickets, he speaks quietly to himself most of the time as he works on the code. Then, he will ask a question somewhat louder and sometimes it seems like he might be asking me but I know at this point he almost never is. :)
So this is not an explanation of Regular Expressions as a tool, that we might use on a daily basis. This is the theoretical basis for how REs is implemented. It's stuff covered in undergrad CS, and one of the next lessons is making your own parser for your own programming language.
The amount of times he wrote return as retrun makes this video super relatable and gives me hope
You've got this bro 💪
I love watching this guy, he looks like some kind of ancient sage like a programming Gandalf
This feels like they edited a 2 hour video, which explained everything, down to 20 minutes :-)
Right back to it, I see! There's an error in the example with the alternating as and bs at 0:59. It should not have a "+" (meaning or) in between "(ab)*" and "(a+ε)"
The green text on the screen for the challenge in the end (20:41) is also incorrect. The one in the comment on the monitor is the correct one.
Prof Altenkirch vids are my favorite!
I love Thorsten. ❤❤ the guy is a true genius of our time.
Another video with Thorsten? Awesome! He has a great sense of humor.
Just watching because of Prof. Altenkirch
Thorsten is amazing, but beyond all of that, a super kind person. Can't believe I've had the chance to interact with him in real life multiple times.
Sure seems like a nice, verysmart guy.
I too watch purely for the fun of (almost~certainly) knowing that if you understand the arcane _jargon_ he is speaking then the _concepts_ are surely simply simple.
LSS: Dude... you had me at "Non-Deterministic Automata"
Is he talking about Regularexprechen?
😏
It would have saved me a lot of time if the mystery regex had been shown correctly on the screen and the paper (from 20:38). The correct regex (with sensible symbols) is /(0|11|10(00|1)*01)*/.
After I had wasted much time on the incorrect one, I drew the AST from the python code in a notebook since I didn't trust the comment above it. The comment was correct as it turned out.
Here's the first matches:
0 : 0
11 : 3 (11)
110 : 6 (11 0)
1001 : 9 (10 01)
1100 : 12 (11 0 0)
1111 : 15 (11 11)
10010 : 18 (10 01 0)
10101 : 21 (10 1 01)
11000 : 24 (11 0 0 0)
11011 : 27 (11 0 11)
11110 : 30 (11 11 0)
I think I can see the pattern.
Ah that's the classical division by 3 test.
The extra credit question on my DFA exam in college was "write a DFA that can determine If a binary number is divisible by 3. Hint, it has 3 states." I recognized the regex instantly.
@@babyeatingpsychopath Technically, shouldn't there be 4 states? The empty string is not "a binary number is divisible by 3", but it *is* your start state. Then you have 3 states for the 3 remainders modulo 3.
@@jursamaj technically, I believe you're correct, I suspect the actual instructions specified a nonzero length binary string. It's been a couple of decades since that exam.
The RE at the end seems to detect binary numbers that are multiple of 3. However, I'm not sure how it checks this.
Yes this is correct. 🎉Maybe I should do another video how to construct it.
@@ThorstenAltenkirch Definitely! And to explain what property of binary numbers you're using in this case.
thank you so much for this serie linking automatons to regexes!
I think Sean has gotten free university degree from making these videos. I hope he gets his diploma at some point
I've always focused on just getting the re to serve some purpose. That's why I got an engineering degree, not a mathematics degree. But this helps me appreciate just how much math is under the hood (bonnet?)! It's fun listening to prof Altenkirsh even though the machine code episode was more my speed
What makes this project particular to "Python" Regular Expressions? Cause re exists and you could roll your own regex in most languages.
Aren't you just making regexes (in some language, that happens to be python)?
great series! i really liked the implementation style
Where is the news about quantum systems
Please change the title of this video. Python is not the important part. People are going to search for help with using regular expressions in Python (import re) and find this video which is not going to help.
If you're watching Computerphile videos and expecting tutorials, you're already in the wrong place.
@@BaronFirespawn Someone who doesn't know computerphile would only see a search result for a popular channel. Regardless, the "Python" in this video had nothing to do with the concept being shown.
Halfway through and I don't understand what's happening...
What's the point? Why Python is important for this?
Yeah, I feel like there's a bunch of missing context
He's implementing regex in terms of an NFA network, in code. He wrote python code for running any NFA network in a previous video. That code will also work on the regex-specific NFA networks he's constructing in this video. He chose Python because it had to be in some programming language, and Python is easier to write than in C for example.
Edit: but yeah as others have said, the title of this video suggests it's about python's re regex library, or just regex in general, which could confuse viewers :/
This is part of a series which is in a playlist. Hopefully that helps you understand the context if you've not seen the previous videos!
TH-cam prompting this episode out the blue. I also bailed halfway through.
This is the university experience. Just throw in you doing a homework assignment for this now, then studying for the exam on it. Somehow by the end you'll look back and realize you absorbed some amount of it because you know more than before you began.
Unit testing should also know the expected result. There should be some instant feedback instead of someone checking and saying, "Yep, that test case must return false, so it's okay".
Yeah... this definitely falls short of proper unit testing. Perhaps Prof. Altenkirch needs to learn to behave... or rather, to learn _behave_ -- the python implementation of the Cucumber conception of unit testing. :)
That final regular expression is just a reformulation of (1(01*0)*1+0)*, obviously.
Now, which is better and why is the real question.
....I have no idea what I've just watched.
I have no idea how he did that. I wonder how many times I have to watch it to figure out what he did?
Also upload videos on compiler design.
I had a problem, so I used regular expression. Now I have two problems.
Prof Altenkirsch is definitely the Alien played by Jemaine Clement in Men in Black. It's so obvious he's a Supermax-escapee from the other side of the moon bent on taking over the world.
Very interesting and recommended gold mine Channel 🎉😊
What about the Fall of Rome where the European people invaded Rome because they where pushed from the east?
Thank you
Which code editor is he using?
One without a code formatter lol
That "In [n]"/"Out [n]" in the console reminds me of spyder, but could be wrong
@@Imperial_Squid well, the title of that window (e.g. at 3:25) says "IPython Console"... you'll also see that sort of output in Jupyter Notebooks... I think a lot of these things are interconnected in some manner, though I don't know the details.
probably Jupyter
e1 = /b?(ab)*a?/
why does he look like an older version of brad pitt as benjamin button
Why care about the POSIX or IETF standard syntaxes for Regular Expressions when you can just make up your own.
For anybody finding this video and wanting to learn regular expressions, go watch a different video.
This is a video about automata on the example of pattern matching and has basically nothing to do with regular expressions at all.
Nice try, but your not going to unconfuse me that easy!
Love regex - hate python (syntax) - useful libraries though.
If python had better syntax and kept the ease of use it would be so nice!
If I can remember the weird quirks in python it is so nice to use
@@XenoTravis it's like a cross between BBC Basic from the 1980s and JavaScript, without any curly braces. And 'elif' - seriously? That just looks like a typo. Deep and shallow copies? Grrrr! Probably all straight forward if you start out learning to code in Python but really annoying if you are previously familiar with other languages. But the libraries are useful.
Oh and why is there a while but not a do ... while ?
What would you improve about the syntax? @@XenoTravis
@@RedHair651 haven't thought about what I would do to improve it tbh. Sometimes it seems a little bit bare and I have to assume a lot of things.
I would change the for loop or at least add in the classic c syntax along with their style. But that is just me being so used to the 'normal' way
The syntax is what you hate? There are way better reasons to hate Python: Mutability. Lack of a type system. Incorrectly / inconsistently-implemented scoping.
Real life Erlich Bachman.
Like if you did not understand a sh*t
Python? Oh, you mean Peißn! Yes, hörd of it.
"My English is not ze yellow from ze egg"
No clue wth is going on here. Thought I was about to listen to a real smart man talk
about using Regular Expressions…
To disjointed to understand unfortunately, gave up at 15min.
0?00
import re already
That really doesn't explain how RE works, which is the whole point of this video
@@DrGreenGiant very much agreed. I wish more was done to draw attention to that distinction, though -- not to mention the fact that he's using a completely different syntax for his regular expressions than anything that's common in the UNIX [and similar] landscape... It's useful stuff if you're thinking about the abstract ideas of it all, but quite disconnected from practical everyday usage of existing implementations. 😕
@@DavidLindes Syntax isn't interesting. It's just arbitrary convention. The fundamental ideas are what matters ... the rest is just implementation details.
@@halfsourlizard9319 Syntax may not be "interesting" to the theory, but it's critically important to actually doing anything useful with actual computers. Also, it can be _very_ interesting -- see the IOCCC.
@@DavidLindes Knowing the theory behind regexps is the interesting bit; there are references (or LLMs) for the derpy idiosyncrasies of the various flavours.
Sorry, I can't learn from this dude.
Please write better unit tests than he does
Only Rust
I don't understand why Rust has so much success
@@RedHair651 A better version of C++, what else do you want? Speed and security. Top-notch for today's needs.
@@RedHair651because rust never sleeps.
First