http://math.stackexchange.com/q/1485260/86776

regexc101.rb

#!/usr/bin/env ruby

n = 10

def test(u, re, goal)
  r = (u =~ re).is_a? Integer
  err = (r != goal)
  w = err ? " ERROR" : ""
  d_e = err ?  1 : 0
  return r, w, d_e
end

def digits(k, base)
  Math.log(k, base).floor + 1
end

k_max = 2**n

puts "Testing \"not containing 101\" for the first #{k_max} non-empty binary words:"

dig_2 = digits(k_max - 1, 2)
dig_10 = digits(k_max - 1, 10)

e1 = 0
e2 = 0
e3 = 0

k_max.times do |k|
  u = k.to_s(2)
  goal = !((u =~ /101/).is_a? Integer)

  r1, w1, d_e1 = test(u, /\A(0*(11*000*)*(10)?)\z/, goal)
  e1 += d_e1

  r2, w2, d_e2 = test(u, /\A(0*((1*00+)*1*0*))\z/, goal)
  e2 += d_e2

  r3, w3, d_e3 = test(u, /\A((0|1+00)*|(0|1+00)*(1+|1+0))\z/, goal)
  e3 += d_e3

  k_pad = sprintf("% #{dig_10}s", k.to_s)
  u_pad = sprintf("% #{dig_2}s", u)
  puts "#{k_pad}: #{u_pad} => goal: #{goal}, r1: #{r1}#{w1}, r2: #{r2}#{w2}, 3: #{r3}#{w3}"
end
puts "errors for regexp 1: #{e1}"
puts "errors for regexp 2: #{e2}"
puts "errors for regexp 3: #{e3}"

puts "done."