<p>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.</p>

CC BY-SA 3.0
2011-10-13T09:45:18.933Z
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.
Max
CC BY-SA 3.0
2011-10-13T09:39:46.647Z
2011-10-13T09:39:46.647Z
Mike B.
<p>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".</p>

<p>For example, we can modify the standard notation as follows to obtain "compressed" regular expressions:</p>

<ul>
<li>You are allowed to remove any prefix that consists of a sequence of ('s</li>
<li>You are allowed to remove any suffix that consists of a sequence of )'s</li>
</ul>

<p>That is, <code>((a|b)*c)de(f|g)</code> can be expressed in the "compressed" notation using, for example, any of the following forms: <code>a|b)*c)de(f|g</code> or <code>((a|b)*c)de(f|g</code> or <code>(a|b)*c)de(f|g)</code>.</p>

<p>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, <code>a|b)*c)de(f|g</code> might represent <code>((a|b)*c)de(f|g)</code> or <code>(((a|b)*c)de(f|g))</code>, but adding extra parentheses does not change the language defined by the expression.</p>

<p>The "compressed" notation is a regular language.</p>

<p>And yes, this is cheating.</p>

CC BY-SA 3.0
2013-11-01T03:10:57.657Z
I didn't quite get this. What about regular expressions that are written as (a(b(c(d*de)f)g)h)? [the final ? is not part of the RE]. In compressed form, does this become: a(b(c(d*de)f)g)h
dhruvbird
CC BY-SA 3.0
2011-10-13T10:35:56.540Z
2011-10-13T10:35:56.540Z
Jukka Suomela
<p>Is it possible to create a regular expression that matches regular expressions in any given notation?</p>

<p>Or, in other words, does there exist a unambiguous and full notation for regular expressions that can be parsed with regular expressions?</p>

CC BY-SA 3.0
2011-10-13T09:47:39.773Z
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?
Max
CC BY-SA 3.0
2011-10-13T10:31:23.953Z
@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.
otto
<regular-expressions><regular-language>
Matching regular expressions using regular expressions
otto
# Matching regular expressions using regular expressions

(Asked by: username_0 on 2011-10-13)

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?

**Tags:** regular-expressions, regular-language
> **Comments:**
> **username_1**: 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?  
> **username_0**: @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.  

---

## 2 answers

### Answer by username_3 on 2011-10-13. Score: 10 | Accepted answer

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.

> **Comments:**
> **username_4**: I didn't quite get this. What about regular expressions that are written as (a(b(c(d*de)f)g)h)? [the final ? is not part of the RE]. In compressed form, does this become: a(b(c(d*de)f)g)h  

---

### Answer by username_2 on 2011-10-13. Score: 4

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.

> **Comments:**
> **username_1**: 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.  

---

