• To: <xml-dev@l...>
• Subject: Re: Validate an XPath with regex
• From: "Gary Stephenson" <garys@i...>
• Date: Tue, 9 Apr 2002 14:49:07 +1000
• References: <8BD7226E07DDFF49AF5EF4030ACE0B7E05573C68@r...>

> I may have barely made it out of my CS Theory class without flunking but
> I do seem to remember that regular expressions and DFAs were equivalent
> while the more powerful PDAs were equivalent to context free grammars. I
> also faintly remember something about context free grammars being higher
> on the Chomsky hierarchy than regular expressions. Hmmmm, I think I need

Apologies for being more than a little "CS Theory" challenged! ;-)

Whilst BNF is used to describe context-free grammars in general, that surely
doesn't prevent particular instances from also being regular - does it?
Thus, the original question comes down to:

Is the XPath grammar equivalent to a regular grammar (ie Chomsky Type 3 )?

I think the answer is "yes" - simply because my XPath processor works for
all the tests I've thrown at it so far (But I'm still by no means certain).

<out-of-my-depth>'ly yrs,

gary

• References:
  • RE: Validate an XPath with regex
    • From: "Dare Obasanjo" <dareo@m...>

• Prev by Date: RE: Validate an XPath with regex
• Next by Date: Re: ?porting DTD namespace support to java [Re: WD for Namespaces 1.1
• Previous by thread: RE: Validate an XPath with regex
• Next by thread: DOM -> HTML ???
• Index(es):
  • Date
  • Thread