Consider the following set constructed with a regular Kleene-star operation: $$ \{10^n \mid n\geq1\}^* $$

Would something like $10100$ be in this set? I know $1010,100100100,1000,$ etc would be, but I'm not sure if you can change $n$ per repetition and have it be something like $10100, 101001010010$, etc.


Short answer: Yes. $10100$ is included.

Long answer:

Let's go through how this particular set is constructed. First, the expression $$ 10^n $$ (in this context) denotes a single string consisting of a $1$ followed by $n$ $0$s (so the string depends on one variable $n$). Then, the set $$ \{10^n \mid n \ge 1\} $$ denotes the set of strings $\{10, 100, 1000, 10000, \ldots\}$. This set can also be denoted using the Kleene-star operation as $100^*$ or $10^+$. Note that this set does not depend on $n$ -- rather, $n$ is just a dummy variable used to describe the elements of the set.

Finally, the set $$ \{10^n \mid n \ge 1\}^* $$ then denotes a concatenated sequence of elements of the original set, like $10100$, $1000$, $1010000010$, etc. When you use the $*$ operation, the string used each time does not have to be the same (that is, you can change $n$ for each repetition). So you can do $10$ first, then $100$, then $10$ again, etc.


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.