Hacker News Reader

Yeah, but regular languages can handle parenthesised expressions up to some const parens-depth, which will be most of the code (for some small constant). And while it might be possible (not quite sure tbh) to express this in star-free manner, the expressions would explode pretty fast in size.

View on HN

I don’t understand how you could express a depth limit with the Kleene star. So its absence would be immaterial to nesting in this context.

Not depth itself, but how using star you can get (ab)* in a much smaller expression than when you want to express it by forbidden patterns for star-free form. And if you nest it a few times r_to get to up to D depth[0] expression grows, but forbidden patterns would grow faster.

[0] e.g. r_1 = (\(\))*, r_d+1 = (\(r_d*\))*

Reply on news.ycombinator.com