Re:Is there a regular expression to detect a valid regular e...
by daveFNbuck on Sunday September 08, 2019 @11:42AM
(#20911180)
If 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)\].
Re:Is there a regular expression to detect a valid regular e...
by repsilat on Sunday September 08, 2019 @11:45AM
(#20911209)
For 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.
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.