0
$\begingroup$

I was reading up about formal languages (see here: https://pdfs.semanticscholar.org/18b2/d685d5e244a6bfc5a31d312f1e8d322c16a9.pdf) and got confused when I started reading about this expression: 0(0+1)∗+(0+1)∗0

This is how I think it works:

The first and last 0 indicates where these two characters must be present. In other words, the string this expression describes must start and end with one 0. (0+1)* describes any combination of 0's and 1's (including none at all), and the plus in between each of these sets of brackets ((0+1)* +(0+1) *) describes a concatenation of these two strings. Therefore, this expression applies to any binary string that begins and ends with a 0.

If this is indeed how the expression works, wouldn't 0(0+1)*0 achieve the same thing?

(Also, is there a site I can check these sorts of expressions? I tried this expression in sites like regex101.com but it didn't work on any of them. This isn't important, I was just curious)

$\endgroup$
0

1 Answer 1

1
$\begingroup$

There are three standard regular expression operators: concatenation, alternation, and Kleene closure. (Note that we're talking about regular expressions in the formal mathematical sense, not the random collections of hacks which comprise typical regex libraries.)

These can be thought of as operators on (possibly infinite sets); alternation is set union, and concatenation of two sets is the Cartesian product; in this sense, alternation and concatenation correspond to addition and multiplication. Alternation is generally written as $+$ (although $\mid$ is also common, because of its use in regexes) while concatenation is generally written without an explicit operator symbol, much the same as mulitiplication.

Kleene closure is a unary operator which produces the arbitrary application of any number of concatenation operations on the same set; in effect, an arbitrarily long concatenation of elements of the set. (It includes 0 concatenations, which is always the empty string.) Kleene closure is always written as a postfix $^*$.

As with algebra, there is a standard operator precedence; Kleene closure binds the most tightly, followed by concatenation, followed by alternation. If you need different binding, you can use parentheses. So $ab^*+cd^*$ should be read as $(a(b^*))+(c(d^*))$, much as you would read the algebraic expression $ab^2+cd^2$

So the expression you ask about:

$$0(0+1)^∗+(0+1)^∗0$$

is the union of two subexpressions: $0(0+1)^∗$ and $(0+1)^∗0$. The first of these is any binary string starting with $0$ and the second is any binary string ending with $0$, so the union is any binary string which starts or ends with $0$; in other words, any binary string which doesn't both start and end with $1$.

$\endgroup$
5
  • $\begingroup$ Thank you so much for your answer. Just for clarification, would (0 ∪ 1) also be acceptable to represent (0+1)? $\endgroup$
    – Jynrei
    Aug 12, 2019 at 2:43
  • $\begingroup$ Sorry, I was thinking over it and wanted to ask something else. Does 0(0+1)*0 not work because there is no alternation/union between the last 0 and the rest of the expression? Thanks. $\endgroup$
    – Jynrei
    Aug 12, 2019 at 2:51
  • $\begingroup$ @jynrei: $0(0+1)^*0$ is all binary strings which start and end with $0$, so it doesn't include either $100$ or $001$, both of which are in the language. $0(0+1)^*+0$ is the same as $0(0+1)^*$, because $0$ is already in that language. $\endgroup$
    – rici
    Aug 12, 2019 at 3:44
  • $\begingroup$ And no, we don't normally write regular languages with $\cup$. $\endgroup$
    – rici
    Aug 12, 2019 at 3:45
  • $\begingroup$ Ah okay, I think I've got it now. Thank you again ^_^ $\endgroup$
    – Jynrei
    Aug 12, 2019 at 8:19

Your Answer

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

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