# Interpretation of this regular expression: (1*0*)*

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 ( )?

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$$.
• 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... – dkaeae Apr 11 at 11:26
• $\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. – 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^*)^*$$.