Do the values of the two * inside the ( ) need to remain unchanged for every repetition of ( )?

For example, 110011001100 is part of this language set, but 1100100010 isn't?

Or can the values of the two * change for every repetition of the ( )?

  • $\begingroup$ @HendrikJan Please don't post answers as comments. $\endgroup$ – David Richerby Apr 11 at 12:56

For any two words $w_1$ and $w_2$, the regular expression $\texttt{((}w_1\texttt{)*(}w_2\texttt{)*)*}$ is equivalent to $\texttt{(}w_1\texttt{|}w_2\texttt{)*}$. Hence, both your examples are elements of the language generated by $\texttt{(1*0*)*}$.

In this setting, it is impossible to specify $w_1$ and $w_2$ occur equally often with a regular expression (except for a finite number of possibilities). Otherwise, you would be able to generate a non-regular language, in this case $\{ 1^n 0^n \mid n \in \mathbb{N} \}^\ast$.

  • $\begingroup$ Thank you. Does that mean (1*0*)^3 = (1*0*)(1*0*)(1*0*)? $\endgroup$ – Shukie Apr 11 at 10:54
  • $\begingroup$ Yes, but that's just how powers of words work. $w^3 = w w w$ for any word $w$ (including when $w$ is a regular expression). I'm not sure how this is relevant to the matter at hand... $\endgroup$ – dkaeae Apr 11 at 11:26
  • $\begingroup$ Just to confirm my understanding that (1*0)^3 doesn't only = (1^a0^b)(1^a0^b)(1^a0^b) and can also be (1^a0^b)(1^c0^d)(1^e0^f). Thanks so much for the explanation. $\endgroup$ – Shukie Apr 12 at 2:15
  • $\begingroup$ $\texttt{(1*0)}$ is just a word (i.e., a series of symbols); this means $\texttt{(1*0)}^3 = \texttt{(1*0)(1*0)(1*0)}$, just like $\texttt{1}^3 = \texttt{111}$. Do not mistake a regular expression for the language it represents! A regular expression is just a word; a language is a set of words. Writing regex $=$ a set of words is wrong in a conceptual level. $\endgroup$ – dkaeae Apr 12 at 11:55

There is no memory in regular expressions. If $R$ is a regular expression, then $R^*$ means "any sequence of strings, each of which matches $R$". So, in your example of $(1^*0^*)^*$, the outer star means "any sequence of strings, each of which matches $1^*0^*$. $110$, $1$, $000$ and $11$ all match $1^*0^*$, so $110\,1\,000\,11$ matches $(1^*0^*)^*$.

Indeed, since $1$, $0$ and $\varepsilon$ all match $1^*0^*$, every binary string matches $(1^*0^*)^*$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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