4 ms·

What is this? I'm so curious but nothing of this rings a bell with me. I mean I know what a regular expression is, and I've formatted several USBs to FAT32, but

by Rokid 6y ago

What is this? I'm so curious but nothing of this rings a bell with me. I mean I know what a regular expression is, and I've formatted several USBs to FAT32, but DFAs and everything in between have me Googling like crazy, still in the dark though.

slondr 6y ago
RegExp and DFAs are the same computation class, so it's useful sometimes to model them as each other.
- Pmop 6y ago
  No idea why you're being downvoted. Also, classical comp. sci technique of reducing your problem into another that's already been solved (with good enough time/mem bounds).
- saagarjha 6y ago
  It’s frequently useful, as many regex engines construct DFAs under the hood :)
  - burntsushi 6y ago
    Not as frequent as you might expect! Most regex engines in common use don't use an automata based implementation, and instead use backtracking. This lets them implement additional non-regular features such as backreferences and recursion. Even automata based regex engines don't usually build up a full DFA, since the size of the DFA may be exponential in the size of the regex. Instead, an NFA similation might be used, or a hybrid NFA/DFA that builds the DFA during match time, but typically doesn't build out the full DFA.
nicholaides 6y ago
It converts your regexp into a virtual filesystem and then you can test if a string matches the regexp by converting the string into a path and testing if that path is contained in the filesystem.
- itronitron 6y ago
  Presumably this is useful if you can place files into (or modify a file at) the location for a particular regexp.
  - Someone 6y ago
    That wouldn’t work. This works by hard linking a lot of directories to each other, so if you were to write a file there, it ends up in multiple locations (possibly all ‘directories’ in the file system) The file system could work around that by creating new unique directories whenever you write any file to an empty directory, but that would require it to keep the regular expression it represents around, and would fill up the file system quite rapidly.
  - duskwuff 6y ago
    I wouldn't necessarily call this useful for anything in particular. It's more of a silly trick to show off than anything. (And a reminder of how regexes work behind the scenes.)
adrianmonk 6y ago
This was what made it all make sense for me: https://perl.plover.com/Regex/article.html https://perl.plover.com/Regex/article.html

by Rokid 6y ago

slondr 6y ago

RegExp and DFAs are the same computation class, so it's useful sometimes to model them as each other.

Pmop 6y ago
No idea why you're being downvoted. Also, classical comp. sci technique of reducing your problem into another that's already been solved (with good enough time/mem bounds).
saagarjha 6y ago
It’s frequently useful, as many regex engines construct DFAs under the hood :)
- burntsushi 6y ago
  Not as frequent as you might expect! Most regex engines in common use don't use an automata based implementation, and instead use backtracking. This lets them implement additional non-regular features such as backreferences and recursion. Even automata based regex engines don't usually build up a full DFA, since the size of the DFA may be exponential in the size of the regex. Instead, an NFA similation might be used, or a hybrid NFA/DFA that builds the DFA during match time, but typically doesn't build out the full DFA.

nicholaides 6y ago

It converts your regexp into a virtual filesystem and then you can test if a string matches the regexp by converting the string into a path and testing if that path is contained in the filesystem.

itronitron 6y ago
Presumably this is useful if you can place files into (or modify a file at) the location for a particular regexp.
- Someone 6y ago
  That wouldn’t work. This works by hard linking a lot of directories to each other, so if you were to write a file there, it ends up in multiple locations (possibly all ‘directories’ in the file system) The file system could work around that by creating new unique directories whenever you write any file to an empty directory, but that would require it to keep the regular expression it represents around, and would fill up the file system quite rapidly.
- duskwuff 6y ago
  I wouldn't necessarily call this useful for anything in particular. It's more of a silly trick to show off than anything. (And a reminder of how regexes work behind the scenes.)

adrianmonk 6y ago

This was what made it all make sense for me: https://perl.plover.com/Regex/article.html https://perl.plover.com/Regex/article.html