4 ms·
This is true if you want to handle arbitrarily deep nested parents. But any given string you are asked to validate to see if it is a regex will be a finite len
by jameshart 7y ago
This is true if you want to handle arbitrarily deep nested parents.
But any given string you are asked to validate to see if it is a regex will be a finite length, and contain a finite number of opening paren characters. So it’s maximum possible nesting depth is known.
And you can construct, fairly trivially, a regex that can validate paren nesting up to a fixed depth.
So, in practice, you could use a regular expression to validate the paren nesting of any given string - if you were allowed to prepare the regex based on the string length, or on running another regex over the string first.
What I suspect you might not be able to validate is that in a regex, while [a-z] is valid, [z-a] is not.
- daveFNbuck 7y agoIf you allow generating a regular expression based on string length, you can validate any computable language with a regular expression. It's trivial to just run a solver on all strings of that length and or the accepted ones together. > What I suspect you might not be able to validate is that in a regex, while [a-z] is valid, [z-a] is not. It's fairly trivial to validate things like a-z being valid in a character class while z-a isn't. There are only finitely many legal ranges. You can just list them all, like \[(a-a|a-b|a-c|...|z-z)\].
- repsilat 7y agoFor a fixed input length all languages are decidable by regular expressions. Trivially, the union of all valid input strings of that length, like "(abc|def|...)". It's not an interesting property.