Is it possible to create a regular expression that matches regular expressions in any given notation?
Or, in other words, does there exist a unambiguous and full notation for regular expressions that can be parsed with regular expressions?
4
$\begingroup$
$\endgroup$
-
4$\begingroup$ What counts as a "notation"? There are countably many regular expressions, and therefore there's an bijection between them and, for example, $a^*$ -- but would you count that as a notation? $\endgroup$ – Max Oct 13 '11 at 9:47
-
$\begingroup$ @Max All right, seems like I fell into a trap when forming this question. As there are several practical ways to write regular expressions I wanted to make the question not specific to any particular one, but as you said, that bijection makes this question trivial, I suppose. $\endgroup$ – otto Oct 13 '11 at 10:31
10
$\begingroup$
$\endgroup$
Even if we require that the expressions are "human-readable", and the conversion between the standard notation and the new notation is fairly easy to compute, the answer is "yes".
For example, we can modify the standard notation as follows to obtain "compressed" regular expressions:
- You are allowed to remove any prefix that consists of a sequence of ('s
- You are allowed to remove any suffix that consists of a sequence of )'s
That is, ((a|b)*c)de(f|g) can be expressed in the "compressed" notation using, for example, any of the following forms: a|b)*c)de(f|g or ((a|b)*c)de(f|g or (a|b)*c)de(f|g).
The compressed notation is unambiguous in the sense that you can recover a semantically equivalent expression by simply adding a sufficient number of leading and trailing parentheses to make everything balanced. Of course, a|b)*c)de(f|g might represent ((a|b)*c)de(f|g) or (((a|b)*c)de(f|g)), but adding extra parentheses does not change the language defined by the expression.
The "compressed" notation is a regular language.
And yes, this is cheating.
-
$\begingroup$ I didn't quite get this. What about regular expressions that are written as (a(b(c(dde)f)g)h)? [the final ? is not part of the RE]. In compressed form, does this become: a(b(c(dde)f)g)h $\endgroup$ – dhruvbird Nov 1 '13 at 3:10
3
$\begingroup$
$\endgroup$
No, it is not possible. You can reduce the language of regular expressions to the language of matching brackets using a homomorphism; As matching brackets is not a regular language, you will neither be able to parse regular expressions with a regular expression.
-
3$\begingroup$ Otto isn't asking about the standard notation for regular expressions. It's not clear every notation is mapped to the Dyck language by a homomorphism (though the obvious candidates of prefix and postfix (Polish and reverse Polish) notation are. $\endgroup$ – Max Oct 13 '11 at 9:45
