A Course on Automata Theory • Hacker News Board

Re: A Course on Automata Theory

#31

Post by dottrap » Thu, Aug 20, 2015, 1:59 PM UTC

forgettableuser wrote: post #29

userbinator wrote: post #15

Earlier quoted context omitted.

Regular expressions are probably one of the most practical and immediately obviously useful things to come out of automata theory.

I already knew Perl and Posix regex when I took automata. I cruised through the initial basics of regular expressions faster than my peers. But I got into trouble after I learned that regex contains a bunch of features (hacks) that have no grounding in pure automata theory. I had to unlearn a whole bunch of things.

Professor Roberto Ierusalimschy (creator of Lua), was bothered by the problems of regex deviating from (real) regular expressions, like how captures create non-determinism, back references make pattern matching algorithms NP complete, no formally defined performance model, and so on. This led him to revisit prior research on PEGs (Parseable Expression Grammars) which are akin to Context-Free Grammars. He created a library called LPeg which was a PEG for Lua.

He gave a talk about all this which can be found here: https://vimeo.com/1485123

So he basically realized people were hacking regular expressions to get more power. So rather than playing that game, he climbed up a level on the automata ladder to get a more mathematically sound approach to the problem.

Re: A Course on Automata Theory

#32

Post by gnuvince » Thu, Aug 20, 2015, 2:14 PM UTC

forgettableuser wrote: post #29

userbinator wrote: post #15

Earlier quoted context omitted.

Regular expressions are probably one of the most practical and immediately obviously useful things to come out of automata theory.

I already knew Perl and Posix regex when I took automata. I cruised through the initial basics of regular expressions faster than my peers. But I got into trouble after I learned that regex contains a bunch of features (hacks) that have no grounding in pure automata theory. I had to unlearn a whole bunch of things.

Regarding that, since I took that class I've been careful about using the term "regular expression" for expressions that describe a NFA and "regex" for what popular languages implement.

Re: A Course on Automata Theory

#33

Post by brudgers » Thu, Aug 20, 2015, 2:24 PM UTC

iso8859-1 wrote: post #26

jimhefferon wrote: post #24

Earlier quoted context omitted.

I'm interested to hear you say this. I teach this course, to students who mostly go on to do Java coding. I have several times run into an old student who told me that they never once used regexes after my class, either in school or in work.

One reason may be that practical regexes have so many extensions that you can't many of the usual tricks on them. http://stackoverflow.com/questions/6363397/how-to-tell-if-on...

I find it helpful to distinguish between "regular expressions" as something mathematical and "regexes" as nebulous more-than an NFA and less than a Turing complete grammar...DFA regex engines being the Platypus that proves the rule.

As soon as you have backtracking and capture groups it's not a regular expression in the mathematical sense. These features make regexes more useful in many simple cases at the cost of making them harder to reason about in more difficult cases.

Re: A Course on Automata Theory

#34

Post by jimhefferon » Thu, Aug 20, 2015, 10:24 PM UTC

varlock wrote: post #28

jimhefferon wrote: post #24

Earlier quoted context omitted.

I'm interested to hear you say this. I teach this course, to students who mostly go on to do Java coding. I have several times run into an old student who told me that they never once used regexes after my class, either in school or in work.

I'm surprised - Did you ask them how do they search for patterns? Entries in log files, function definitions or usage in code, matching files in a shell?

> Did you ask them how do they search for patterns? Entries in log files, function definitions or usage in code, matching files in a shell?

You know, I have. In some ways it is like communicating across cultures in that the question does not seem to make all that much sense to them. That I can tell, they don't ever search for patterns. The would look for that feature in their GUI log reading program, I suppose.

Failing that, they would write code, 100% in Java I think, and I suppose that if they had to do what I would reach for a regex to do, they would write code to do it. (Is this what jwz means by "Now they have two problems," that they should do the job in code?)

But, again, I don't think there is a real communication there. I'm not too sure what they mean and they look like they do not recognize the situations I ask about.