4 ms·
Do you know whether the restrictions you're talking about limit regexps to the set of actual regular languages?
by bdr 17y ago
Do you know whether the restrictions you're talking about limit regexps to the set of actual regular languages?
- crux_ 17y agoThe algorithm I used should work with anything that's a "Regular Hedge Grammar". An off-the-cuff understanding is that means a regular hedge grammer is a CFG written such that any recursion in the grammar is tail-recursion. (Hopefully that makes sense, although I'm mixing terms from different domains there.) So, yes. (n.b.: I haven't worked much with the theory; just implemented a couple of papers. :) )
- baddox 17y agoI'm not understanding what you're saying. Whether a grammar on one level of the Chomsky hierarchy is also a grammar on a lower level is an undecidable problem.
- alttab 17y agoI'd think so. Certain types of recursion or undefinable branches leads to unprovable expressions.