On Fri, Aug 09, 2002 at 05:23:58PM -0700, Steve Fink wrote: > Wow. Since you went to the trouble of writing all this up, it really > ought to go in a FAQ somewhere. It probably already is in a FAQ somewhere; I just don't know where. :)
> On Thu, Aug 08, 2002 at 12:05:00AM -0400, Mark J. Reed wrote: > > Finite state machines can match regular expressions whose only operations > > are closure (*), alternation (|), and grouping. Some of the other things > > Don't forget optional subexpressions (?). Not sure what the official > name is. Don't need 'em. a? === (a|) (a or nothing). > They can also handle negation, but nobody ever seems to put that into > the regex syntax. Probably because the exact semantics get fuzzy when > you're not anchored at the beginning and end, and any particular > semantics you might pick are deceptive and/or useless. Hm. Not sure about negation. > And if you implement the NFA the way you're implying (as a traditional > NFA), you'll always get the same answer to whether or not the > expression matches, but assuming the answer is yes the NFA and DFA > might match different parts of the string. Which doesn't contradict > anything you're saying, but it's good to be aware that the theoretical > purpose for these things (deciding whether a given string matches an > expression or not) is not the same as the common practical purpose > (finding the exact substring within a given string that matches the > expression). True. > > (Historically, the grep program has used an NFA, while egrep has > > used a DFA.) > > That sounds backwards. It's not. It was the example our prof used, and it's also that way in table 4-1 of _Mastering_Regular_Expressions_. > You should probably also mention somewhere that once you break free of > the bounds of regularity, it's much easier to implement many features > and irregular constructs with an NFA rather than a DFA. Like capturing > parentheses, alternation that prefers the choice the expression gives > first, etc. True. Although with a DFA there's not much reason to add preferential alternation since it matches just as fast no matter which alternate matches. > Anyone happen to know where pushdown automata fit in this list? Can > they handle context-sensitive, just context-free, or some other > subset? The set of languages recognizable by pushdown automata (PDAs) is exactly the set of context-free languages. To recognize a context-sensitive language I think you need a Turing machine. I'm not aware of anything intermediate in power between a PDA and a TM. -- Mark REED | CNN Internet Technology 1 CNN Center Rm SW0831G | [EMAIL PROTECTED] Atlanta, GA 30348 USA | +1 404 827 4754 -- "Help, Mr. Wizard!" -- Tennessee Tuxedo
