Prints all n-bit strings that do not contain the pattern 010

[shaq]

Dear all,

I have a little programming problem of discrete mathematics.

Question: Write a program that prints all n-bit strings that do not contain the pattern 010.

Someone helps me?

 

[wsalem]

Re: Prints all n-bit strings that do not contain the pattern

I assume you meant a function that examines the string as a whole and tells if your string contained 010 or not?

Define a function with input a string and a boolean output (True if 010 is found, False otherwise)
Define boolean variables A,B := False, False
foreach char in string:
if ~A & ~B & char = '0': B := ~B (pattern '0' found, state goes from 00 to 01)
elseif ~A & B & char = '1': A := ~A, B :=~B (pattern '01' found, goes state from 01 to 10)
elseif A & ~B & char = '0': return True (pattern '010' Found, return True)
elseif A & ~B & char = 1: A := ~A (pattern '011' found, return to initial state 00)
endfor
return False


Some conditions are omitted as they don't change the state,
When state is 00 and it finds a '1', there's no transition here! Similarly, when in state 01 and find a '0', it stays at 01 as if the new zero is the first in the pattern 010 to be expected!
Also the state don't have to be two boolean variables, it can be anything as long as it can have three unique state (an integer from 0 to 2, a character taking a,b,c, .....)