From mboxrd@z Thu Jan 1 00:00:00 1970 From: "Brian L. Stuart" To: Fans of the OS Plan 9 from Bell Labs <9fans@9fans.net> Date: Mon, 27 Oct 2008 16:13:46 +0000 Message-Id: <102720081613.1191.4905E8BA00036821000004A722230647629B0A02D2089B9A019C04040A0DBF9B9D0E9A9B9C040D@att.net> In-Reply-To: <7F426112C3E059066F0024AE@[192.168.1.2]> References: <45432371edb2231a8b90975a0efdf7bb@terzarima.net> <7F426112C3E059066F0024AE@[192.168.1.2]> Subject: Re: [9fans] non greedy regular expressions Topicbox-Message-UUID: 28bbe52c-ead4-11e9-9d60-3106f5b1d025 > The set of "big books on regular expressions" includes Jeffrey Friedl's > "Mastering Regular Expressions" that happens to contain a chapter by the > title "NFA, DFA, and POSIX" wherein he says: > > > DFA Speed with NFA Capabilities: Regex Nirvana? This guy seems to blur the distinctions here. His discussion makes it sound like he's saying that NFAs have more expressive power than DFAs. This is incorrect. Both NFAs and DFAs have exactly the same expressive power as the class of grammars called regular. For the arbitrary case of nesting (e.g. parens), these machines are insufficient. However, for any prescribed maximum nesting level, you can write a regular expression to account for it, though it becomes clumsy. To get more expressiveness, you need to go to a machine with more functionality. Classically, the next step up the hierarchy is the pushdown automaton. The expressive power of this machine corresponds directly to the context- free grammars. Because the full generality of the CFG require nondeterminism, automated translations from CFG to code/machine are usually done with restricted classes of CFGs, such as LR(k) and LALR. You can also increase the power of a FA by adding a counter or by making the transitions probablistic. If you truly want to build expression matching mechanisms that go beyond regular, building on the FA with counter(s) would be a far more sound foundation than a lot of the ad hoc stuff that's been done. But the truth is that whipping up a CFG and feeding it to yacc is far more expedient than torturing regular expressions all day. > Again, turns out the "big books on regular expressions" can give the > lowlife--that's me--things "hackers" deny them. And a good book on automata theory can give you far more than any "big book of...", "... in 21 days" or "... for dummies" book can. Besides, why would you think that anyone is denying you knowledge or the opportunity to write code that demonstrates your ideas? BLS