First of all, thanks for the explanation. It's above my head, but thanks
anyway.
This guy seems to blur the distinctions here. His discussion
He doesn't. If one reads the whole section part of which was quoted one
will see that he clearly states DFA and NFA are theoretically equivalent,
but then goes on to explain that DFA and NFA _implementations_ are not
identical.
The true mathematical and computational meaning of "NFA" is different
from what is commonly called an "NFA regex engine." In theory, NFA and
DFA engines should match exactly the same text and have exactly the same
features. In practice, the desire for richer, more expressive regular
expressions has caused their semantics to diverge. An example is the
support for backreferences.
The design of a DFA engine precludes backreferences, but it's a
relatively small task to add backreference support to a true
(mathematically speaking) NFA engine. In doing so, you create a more
powerful tool, but you also make it decidedly nonregular (mathematically
speaking). What does this mean? At most, that you should probably stop
calling it an NFA, and start using the phrase "nonregular expressions,"
since that describes (mathematically speaking) the new situation. No one
has actually done this, so the name "NFA" has lingered, even though the
implementation is no longer (mathematically speaking) an NFA.
-- from the same book
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?
Because lowlifes don't write code. No need for somebody to stop them from
doing so. They learn slowly, hardly, painfully--they aren't smart. If
possible they'll learn less rather than learn more. What the "hacker"
denies the lowlife is the opportunity to exist free of "GNU-is-wrong" or
"X-is-wrong" blemish. GNU may be wrong, or right, but GNU is learnt fast
and easy. And it does the job.
By the way, Friedl's book has the advantage of giving a lowlife a glimpse
of a subject otherwise arcane from that same lowlife's point of view. It's
good--for the lowlife, of course--to know the wonders they see didn't
spring into existence out of the blue. I benefitted from that learning.
--On Monday, October 27, 2008 4:13 PM +0000 "Brian L. Stuart"
<[EMAIL PROTECTED]> wrote:
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
