Proving that a specific string in in a set of strings

Question

Consider the set of strings defined recursively as follows

Suppose there is a set of strings L ⊆ {0,1}∗ which means L can contain any string of any length that can contain any combination of 0 and 1.

This has a property of:

• The empty string " is in L.
• For any string x in L, the string 0x is also in L.
• For any strings x and y in L, the string 1x1y is also in L.
• These are the only strings in L.

I want to prove that the string 101110101101011 is in L.

How can I use the properties stated above to prove this with valid reasons?

Answer 1

( There's probably a much nicer way to do this. )

Let's number the properties

1• The empty string " is in L.

2• For any string x in L, the string 0x is also in L.

3• For any strings x and y in L, the string 1x1y is also in L

for easier reference. I'm going to work from the end of the string to the beginning.

Applying 3) to x=", y=" shows $11$ is in L.

Known elements of L={11}

Applying 2) to x=" shows $0$ is in L.

Known elements of L={11, 0}

Applying 2) to x=$11$ shows $0\underline{11}$ is in L.

Known elements of L={11, 0, 011}

Applying 3) to x=$0$, y=$011$ shows $1\underline{0}1\underline{011}$ is in L.

Known elements of L={11, 0, 011, 101011}

Applying 3) to x=$0$, y=$101011$ shows $1\underline{0}1\underline{101011}$ is in L.

Known elements of L={11, 0, 011, 101011, 101101011}

Applying 2) to x=$101101011$ shows $0\underline{101101011}$ is in L.

Known elements of L={11, 0, 011, 101011, 101101011, 0101101011}

Applying 3) to x=$011$ and y=$0101101011$ shows $1\underline{011}1\underline{0101101011}$ is in L.

Known elements of L={11, 0, 011, 101011, 101101011, 0101101011, 101110101101011}

Answer 2

First of all let's be more careful on how things are stated. This is how I would restate your problem:

Problem. Let $L \subseteq \{0,1\}^*$ be a set of strings such that:

• (1) The empty string is in $L$.
• (2) For any string $x$ in $L$, the string $0x$ is also in $L$.
• (3) For any strings $x$ and $y$ in $L$, the string $1x1y$ is also in $L$.
• (4) These are the only strings in $L$.

Show that $101110101101011 \in L$.

You said:

which means L can contain any string of any length that can contain any combination of 0 and 1.

Depending on how that sentence is interpreted, it isn't really true. Note that from the definition above, the string $10$ is not in $L$. In fact, any string with an odd amount of $1$s is not in $L$.

Now, to the proof. From the first and second points, we get that any sequence of zeros is in $L$.

Whenever I "take out" a digit in the proof, I will put an underscore to improve readability. Treat the underscore as an empty string.

From (3), to prove that $\text{101110101101011} \in L$ it suffices to prove that $\text{___110101101011} \in L$. From (3), to prove that $\text{___110101101011} \in L$ it suffices to prove that $\text{_____0101101011} \in L$. From (2), to prove that $\text{_____0101101011} \in L$ it suffices to prove that $\text{______101101011} \in L$. From (3), to prove that $\text{______101101011} \in L$ it suffices to prove that $\text{_________101011} \in L$. From (3), to prove that $\text{_________101011} \in L$ it suffices to prove that $\text{____________011} \in L$. From (2), to prove that $\text{____________011} \in L$ it suffices to prove that $\text{_____________11} \in L$. From (3), to prove that $\text{_____________11} \in L$ it suffices to prove that $\text{_______________} \in L$, which is true by (1).

Answer 3

These three properties can be seen as operations, you can take a string from $L$, add a bunch of zeroes in the front and you'll still be in $L$. Or you can take two strings from $L$, add ones in the front and concatenate the results.

Let me add a simple python script which checks if a string belongs to $L$:

def go(s):
  if len(s) == 0:
    return (True, [])
  print(s)
  if s[0] == '0':
    g = go(s[1:])
    return (g[0], ['0', s[1:]])
  for i in range(0, len(s) - 1):
    g1 = go(s[1: i + 1])
    if (s[i + 1] != '1'):
      continue
    g2 = go(s[i + 2:])
    if not(g1[0] and g2[0]):
      continue
    return (True, [s[1: i + 1], s[i + 2: ]])
  return (False, [])    

print(go('101110101101011'))