Can you help me mathematically describe this pattern?

[farkuldi]

Hello,

This is a simple question, but I don't remember how to do it. I am working with a computer program someone else wrote to generate some strings of numbers, and I need to know the syntax for describing the pattern of these numbers. I have determined the characteristics of all the possible numbers the program could generate (it's not complicated), but I need help translating it into mathematical language. So here goes.

The program only generates 1s and 0s, and concatenates them into one large string.

A string of length two can be generated, but it must be "11."

Strings of length one, three, four, or five are impossible.

Strings of length six must have a sequence of four consecutive 1s in the second through fifth positions, i.e., ?1111? (the question marks can be either zero or one).

Strings can be greater than length six, but there must always be this same ?1111? placed somewhere in the string, so ?1111? is allowed, ?1111?? is allowed, ?1111?? is allowed, and so on. As long as ?1111? appears somewhere in the string, it is legal.

Can someone please explain how I can describe this mathematically?

Thanks in advance for any help.

 

[economicsnerd]

Sounds like s is a valid string if and only if either s=11 or there exist (non-null) strings t,u such that s=t1111u. Am I interpreting correctly?

 

[farkuldi]

Sounds like s is a valid string if and only if either s=11 or there exist (non-null) strings t,u such that s=t1111u. Am I interpreting correctly?

Well yes, but the substrings s and t would have to be composed of only ones and zeroes. I think the important thing is that, other than the special case of the two character string 11, a string must contain at least four consecutive ones, and those four consecutive ones must have at least one character on either side of them.

So basically we could have 11010111110, 0111111, 0101011110, 011110010101, etc.

I was hoping for a more numerical way of describing the set of possible strings, i.e. set notation (?) or similar.

Thanks for your reply!

 

[jbriggs444]

Sounds like a job for a regular expression (regex).

^11$|^[01]+1111[01]+$

Vertical bar means alteration -- choose one or the other. It binds loosely.
^ means beginning of string.
$ means end of string.
[] surrounding a list of characters matches any character in the list
+ means that the preceding element may be repeated one or more times

You could also do it with Bachus-Naur form (BNF)

 

[farkuldi]

Hehe, I'm quite familiar with regular expressions and was going to fall back to using one if I couldn't find anything else, so I guess we think alike! However, I just thought I could do it in something less computer science-y and more along the lines of formal mathematical notation. For some reason, set notation kept sticking in my mind.

I do have a grammar which I could easily put into Bachus-Naur form, but that is what I am trying to get away from.

Thank you. :)

 

[economicsnerd]

The set of such strings is \{(1,1)\}\cup\left[\left(\bigcup_{k=1}^\infty\{0,1\}^k\right)\times \{(1,1,1,1)\}\times \left(\bigcup_{k=1}^\infty\{0,1\}^k\right) \right], but writing it in this "more precise" way doesn't add any clarity.

 

[farkuldi]

The set of such strings is \{(1,1)\}\cup\left[\left(\bigcup_{k=1}^\infty\{0,1\}^k\right)\times \{(1,1,1,1)\}\times \left(\bigcup_{k=1}^\infty\{0,1\}^k\right) \right], but writing it in this "more precise" way doesn't add any clarity.

Thank you, that is what I was hoping for. I wasn't looking for precision of clarity; I just wanted to know the formal way to describe it. Now I see. I'd better go brush up on my set notation now so that I can remember how to read it.

Thanks again.