<p>First of all, in order to avoid confusion with the parenthesis found in a regular expression, I will use the characters $[$ and $]$ instead of parenthesis in my strings.</p>

<p>I can't tell from the question whether you want the strings in $L$ to be validly parenthesized. </p>

<p>One way I an interpret your question is that you want the strings of your language to be validly parenthesized. You can then use the following regular expression: <code>(a | b | [(a | b)*])*</code></p>

<p>The other way I can interpret your question is that the strings of your language do not have to be validly parenthesized; for example, $aba[b \in L$. Under this interpretation, the reason that the string $[a[a$ is not in $L$ is that it contains two open parenthesis in a row (ignoring $a$s and $b$s). The rule for $L$ with this interpretation is that a string is in $L$ if and only if removing all the $a$s and $b$s results in an element of <code>(ε | ])([])*(ε | [)</code>.</p>

<p>In this case, simply inserting $a$s and $b$s everywhere gives us the regular expression <code>(a | b)*(ε | ])((a | b)*[(a | b)*])*(a | b)*(ε | [)(a | b)*</code>.</p>

CC BY-SA 3.0
2015-09-06T18:09:43.630Z
2015-09-06T18:09:43.630Z
Mikhail Rudoy
<p>Let character set $\Sigma=\{a,b,(,)\}$. I want to write a regular expression for the language $L$ that does not have a parenthesis inside a parenthesis.</p>

<p>For example, $(abaab)(bbbaa) \in L$, while $(abb(abb)bb) \not\in L$. Also $(a(a \not \in L$. </p>

<p>I cannot think of a good way to write a regular expression for $L$.</p>

<fl.formal-languages><automata-theory><regular-language><regular-expressions>
Writing a regular expression for character set $\Sigma = \{a,b,(,)\}$ that not have a parenthesis inside a parenthesis
rega
# Writing a regular expression for character set $\Sigma = \{a,b,(,)\}$ that not have a parenthesis inside a parenthesis

(Asked by: username_0 on 2015-09-06)

Let character set $\Sigma=\{a,b,(,)\}$. I want to write a regular expression for the language $L$ that does not have a parenthesis inside a parenthesis.

For example, $(abaab)(bbbaa) \in L$, while $(abb(abb)bb) \not\in L$. Also $(a(a \not \in L$.

I cannot think of a good way to write a regular expression for $L$.

**Tags:** fl.formal-languages, automata-theory, regular-language, regular-expressions


---

## 1 answers

### Answer by username_1 on 2015-09-06. Score: 1

First of all, in order to avoid confusion with the parenthesis found in a regular expression, I will use the characters $[$ and $]$ instead of parenthesis in my strings.

I can't tell from the question whether you want the strings in $L$ to be validly parenthesized.

One way I an interpret your question is that you want the strings of your language to be validly parenthesized. You can then use the following regular expression: `(a | b | [(a | b)*])*`

The other way I can interpret your question is that the strings of your language do not have to be validly parenthesized; for example, $aba[b \in L$. Under this interpretation, the reason that the string $[a[a$ is not in $L$ is that it contains two open parenthesis in a row (ignoring $a$s and $b$s). The rule for $L$ with this interpretation is that a string is in $L$ if and only if removing all the $a$s and $b$s results in an element of `(ε | ])([])*(ε | [)`.

In this case, simply inserting $a$s and $b$s everywhere gives us the regular expression `(a | b)*(ε | ])((a | b)*[(a | b)*])*(a | b)*(ε | [)(a | b)*`.


---

