0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ The regular expression + operator is just syntactic sugar for one or more. So x+ is equivalent to xx* $\endgroup$
    – tripleee
    Commented Oct 7, 2024 at 9:39
  • $\begingroup$ According to Peter Linz (in "an introduction to formal languages and automata"), in regular expressions '+' means OR $\endgroup$
    – Teresa Salazar
    Commented Oct 7, 2024 at 10:15
  • $\begingroup$ 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. $\endgroup$
    – tripleee
    Commented Oct 7, 2024 at 10:18
  • $\begingroup$ 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. $\endgroup$
    – Teresa Salazar
    Commented Oct 7, 2024 at 12:48
  • 3
    $\begingroup$ 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 cs.stackexchange.com . $\endgroup$
    – Emil Jeřábek
    Commented Oct 7, 2024 at 13:15

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.