Hacker News new | ask | show | jobs
by chrisseaton 2083 days ago
I don't think you need the Kleene star to be regular.

Star-free languages are regular languages without the Kleene star.

https://en.wikipedia.org/wiki/Star-free_language

But I'm not an expert in formal languages and maybe you are.

1 comments

I think you're slightly at cross-purposes: GP is saying that since globs lack the Kleene star, they cannot be used to define all regular languages.

Star-free languages are a strict subset of the set of regular languages, so there exist regular languages that require the Kleene star to be represented as a regular expression; indeed the Wikipedia article you linked gives an example.

It's perhaps worth noting that neither regular expressions nor globs are themselves regular languages: they are just used to define regular languages. Consider that regular expressions usually require some form of parenthetical notation, and that languages with matched parentheses cannot be regular as a trivial consequence of the pumping lemma.