stringsetautomata

The set of all strings over {0,1} that do not contain both the sequence “101” and the sequence “010”

I want to write the set of all strings over {0,1} that do not contain both the sequence “101” and the sequence “010” formally.

Is that correct:

{w∈{0,1}* | ∀x,y∈{0,1}s.t w = x101y ⇔ ∀x',y'∈ {0,1},w ≠ x'010y'}

Thanks!

Solution

  • I will write it with words, because of lack of time:

    w in {0,1}* where w does not belong to (x union y), x = a101b, y = c010d, for any a,b,c,d in {0,1}*.