Hacker News Reader

Funnily enough in computer science-land the often used model for transformsers corresponds to (heavily compressed) star-free languages, languages without counters, that specifically can't count things, like opening parentheses. This is rather theoretical though, because of the size of constants involved.

View on HN

Star-free languages are a subset of regular languages (i.e. matchable by a regular expression), which programming languages generally aren’t anyway?

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.

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