-2
$\begingroup$

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$.

$\endgroup$

closed as off-topic by Kaveh, Hsien-Chih Chang 張顯之, Jukka Suomela, Sasho Nikolov, R B Sep 7 '15 at 5:31

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, Hsien-Chih Chang 張顯之, Jukka Suomela, Sasho Nikolov, R B
If this question can be reworded to fit the rules in the help center, please edit the question.

1
$\begingroup$

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)*.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.