[Math] Kleene Closure and determining whether a string x is in a set

discrete mathematicsregular expressions

If I'm given the following string $11101$, how do I know if it is in the following sets or not?

$$\{11\}^*\{01\}^*$$

or

$$\{111\}^*\{0\}^*\{01\}$$

from what I understand a Kleene Closure ($A^*$) of set $A$ is a set that has a concatenation of arbitrary strings from $A$. I'd prefer an answer that teaches me why 11101 is not in the first set but it is in the second.

Best Answer

A string belongs to the set $\{11\}^*\{01\}^*$ if and only if it can be written in the form $(11)^m(01)^n$ for some non-negative integers $m$ and $n$: it must be the result of concatenating $m$ copies of $11$ and $n$ copies of $01$ for some integers $m,n\ge 0$. The length of the string $(11)^m(01)^n$ is $2m+2n$, which is clearly always even. The length of the string $11101$, on the other hand, is odd, so $11101\notin\{11\}^*\{01\}^*$.

Showing that a string is not in a given set typically requires some sort of general argument, as in the previous paragraph, or a rather tedious syntactic analysis (see the addendum below). Showing that $11101\in\{111\}^*\{0\}^*\{01\}$, on the other hand, merely requires us to decompose $11101$ in a way that shows its membership in the set $\{111\}^*\{0\}^*\{01\}$. By definition every member of this set must have the form $(111)^m0^n01$ for some non-negative integers $m$ and $n$: it must be obtained by concatenating zero or more copies of $111$ with zero or more copies of $0$ and exactly one copy of $01$, in that order. Can we write $11101$ in that form? Sure: $11101=(111)^10^001$. That is, we can concatenate one copy of $111$, no copies of $0$, and the required single $01$ to form $11101$.

Added: It’s a bit tedious, but we can show that $11101\notin\{11\}^*\{01\}^*$ by thinking of $\{11\}^*\{01\}^*$ as a pattern, attempting to match $11101$ to that pattern, and showing that this can’t be done. It’s clear that if $\color{red}{11}101\in\{11\}^*\{01\}^*$, the $\color{red}{11}$ must belong to $\{11\}^*$. But the remaining $101$ starts with $10$, which belongs neither to $\{11\}^*$ nor to $\{01\}^*$, so there’s no way to continue the matching. Since the initial match of the $\color{red}{11}$ is forced, we’re stuck, and $11101$ cannot belong to $\{11\}^*\{01\}^*$.