[
Lists Home |
Date Index |
Thread Index
]
> 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
|
