#!/bin/sh
# For each of the 11 regular expressions obtained from factoring the
# automaton for "1|10|100" in all possible ways, check which of the
# counter-example strings it accepts.
# An accepted string is replaced by the automaton name in the output.
# (Automata are named by the factoring equivalence relation on
# the state set {a,b,c,d}).

for  a in                                                       \
        's/+ \(1\|10\|100\) +/+ a,b,c,d +/'                     \
        's/+ \(1*\|1*0\|1*00\) +/+ a=b +/'                      \
        's/+ \(1*0*\) +/+ a=b,c=d +/'                           \   
        's/+ \(\(0\|1\)*\) +/+ a=b=c=d +/'                      \
        's/+ \(\(100\)*\|\(100\)*1\|\(100\)*10\) +/+ a=d +/'    \
        's/+ \(\(1\|00\)*\|\(1\|00\)*0\) +/+ a=b=d +/'          \
        's/+ \(\(10*0\)*\|\(10*0\)*1\) +/+ a=d,b=c +/'          \
        's/+ \(10*\) +/+ b=c=d +/'                              \
        's/+ \(\(0\|10\)*\|\(0\|10\)*1\) +/+ a=c=d +/'          \   
        's/+ \(\(10\)*\|\(10\)*1\|\(10\)*0\) +/+ a=c +/'        \   
        's/+ \(\(00\|10\)*\|\(00\|10\)*\(0\|1\)\) +/+ a=c,b=d +/'
do

    # optical separator:
    echo "++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++"

    # somewhat beautified regular expression, and automaton name:
    echo "$a" | sed '
                s,\\,,g
                s,\*,",g
                s,s/+ (,,
                s,) +/+ ,\t\t,
                s,+/$,,
                '

    # result of applying the reg.exp. to the counter-example strings:
    sed -e "$a" <<EOF
                + 11 + 11 +
                + 1001 + 1001 +
                + 101 + 101 +
                + 0 + 0 +
EOF

done