<p>How can I write the following regular expression into set theory? <code>0*1(0+10*1)*</code></p>
<p>Is any of the following correct?</p>
<ul>
<li><span class="math-container">$$ \{0*1(0+10*1)*\}$$</span></li>
<li><span class="math-container">$$ \{0^n 1 (0 + 1 0^m 1)^p, n&gt;=0, m&gt;=0, p&gt;=0\}$$</span></li>
<li><span class="math-container">$$ \{w 1 v, w ∈ \{0\}*, v ∈ \{x,z\}*, x=\{0\}*, z=\{10*1\}\}$$</span></li>
</ul>
<p>The problem is with the '+' operator, which I don't know if it is possible to have in set theory notation.</p>

CC BY-SA 4.0
2024-10-07T09:39:19.357Z
The regular expression `+` operator is just syntactic sugar for one or more. So `x+` is equivalent to `xx*`
tripleee
CC BY-SA 4.0
2024-10-07T10:15:51.807Z
According to Peter Linz (in "an introduction to formal languages and automata"), in regular expressions '+' means OR
Teresa Salazar
CC BY-SA 4.0
2024-10-07T10:18:34.807Z
There are several competing formalisms; you are probably reading the wrong one. The example in your question (which is malformatted; I submitted an edit suggestion, but you'll have to approve it) looks like Unix regex (i.e. Thompson's `grep` plus Aho's "extended" syntax) but perhaps you should clarify with whoever gave you the assignment if you are unsure.
tripleee
CC BY-SA 4.0
2024-10-07T12:48:59.903Z
Yes, you are right, it was malformatted, thank you for editing. 
The exercise is to write the language accepted by an automata using set notation. I know what regular expressions are and that is why I wrote it in regular expression using the notation by Peter Linz that we use in class. However, I have trouble with the notation used in sets. Specifically, I don't know which of the three notations is best.
Teresa Salazar
CC BY-SA 4.0
2024-10-07T13:15:12.880Z
Disregarding what the correct notation is, this is not a research-level question, and it is off-topic on this site. It may be more appropriate at https://cs.stackexchange.com .
Emil Jeřábek
<regular-expressions><set-theory><notation>
Regular Expression to set theory
Teresa Salazar
# Regular Expression to set theory

(Asked by: username_0 on 2024-10-07)

How can I write the following regular expression into set theory? `0*1(0+10*1)*`

Is any of the following correct?

* $$ \{0\*1(0+10\*1)\*\}$$
* $$ \{0^n 1 (0 + 1 0^m 1)^p, n>=0, m>=0, p>=0\}$$
* $$ \{w 1 v, w ∈ \{0\}\*, v ∈ \{x,z\}\*, x=\{0\}\*, z=\{10\*1\}\}$$

The problem is with the '+' operator, which I don't know if it is possible to have in set theory notation.

**Tags:** regular-expressions, set-theory, notation

> **Comments:**
> **username_1**: The regular expression `+` operator is just syntactic sugar for one or more. So `x+` is equivalent to `xx*`  
> **username_0**: According to Peter Linz (in "an introduction to formal languages and automata"), in regular expressions '+' means OR  
> **username_1**: There are several competing formalisms; you are probably reading the wrong one. The example in your question (which is malformatted; I submitted an edit suggestion, but you'll have to approve it) looks like Unix regex (i.e. Thompson's `grep` plus Aho's "extended" syntax) but perhaps you should clarify with whoever gave you the assignment if you are unsure.  
> **username_0**: Yes, you are right, it was malformatted, thank you for editing.  The exercise is to write the language accepted by an automata using set notation. I know what regular expressions are and that is why I wrote it in regular expression using the notation by Peter Linz that we use in class. However, I have trouble with the notation used in sets. Specifically, I don't know which of the three notations is best.  
> **username_2**: Disregarding what the correct notation is, this is not a research-level question, and it is off-topic on this site. It may be more appropriate at https://cs.stackexchange.com .  

---

## 0 answers

