# Kleene Closure and determining whether a string x is in a set

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.

-

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\}^*$.

-
Perfect answer. –  user1766888 Dec 2 '12 at 0:01
@user1766888: Thank you. –  Brian M. Scott Dec 2 '12 at 0:03
I disagree that "Showing that a string is not in a given set typically requires some sort of general argument". This is precisely what parsing algorithms do, and any parsing algorithm can be implemented so as to deliver a proof of non-matching when executed on a non-matching string. In this particular case the generated proof would begin with a case analysis of whether the string 11101 began with 0 or 1 instances of 11, or 2 or more (no), and then in each of the former cases whether it could continue with 01 (no). –  MJD Dec 2 '12 at 0:12
@MJD: You’re right. I thought about expanding the answer to include a syntactic analysis (= attempted parse) of $11101$, decided not to, and then forgot to mention it. I think that I’ll go back and add it. –  Brian M. Scott Dec 2 '12 at 0:16
For the first set, you could also use a parity argument on the length of the string. –  Ben Alpert Dec 2 '12 at 1:08
show 3 more comments