Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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