Question

Bit String Recursion Help. Question attached

Answer 1

is this correct?
Given the set
"S=" {0^r 1^s 0^r│r,s ∈N}
S is the set of all the bit strings that are at least of length 3, where the number of 0’s must be equal but the number of 1’s can be different than the number of 0’s.
Then,
"S={010,00100,001100,00011000,…}"
We can define the set S recursively by having an
Initial condition:
"0" "1" ^"n" "0 ∈ S,n ∈ N"
And proposing a
Recursive step
"if w ∈S,then 0w0 ∈S"

Answer 2

I don't get your initial condition.

Answer 3

Also, what class is this? What operations are you allowed to use?

Answer 4

\[01^n0 \in S , n \in N \]

Answer 5

Discrete Mathematics one, in the topic of Recurrence and Bit Strings. It is so very confusing and we are not getting a good explanation

Answer 6

I agree with you on that.

Answer 7

This reminds me of context-free grammars.

Answer 8

What you have looks okay, but you could take it even a step further.

Answer 9

I would take your advice. How can I do it?

Answer 10

Have a new set, we can call it \(T\).
Our initial step: \(1\in T\)
First recursive step: \(t\in T\implies 1t \in T\).
Second recursive step: \(x\in T \cup S \implies 0x0 \in S\).

Answer 11

This is just allowing us to define \(T\) as \(1^n\).

Answer 12

For a context free grammar, this would be written as: \[
T \to 1\\
T\to 1 T\\
S \to 0T0\\
S\to 0S0
\]

Answer 13

ahh I see! Thanks!

Answer 14

You build up. which is the purpose of recurrence right?

Answer 15

I suppose so. My interpretation was that you want to get rid of any exponents, and keep everything to a simple concatenation operation.

Answer 16

This question seems like something out of Automata Theory, so having it in discreet math seems a bit weird to m e.

Answer 17

The class is so very alien lol I wish it was taught differently in a more Plain English way. BUt thanks for your help. thanks a lot