ANSWERS TO RE/FSA EXERCISES

 1. Easy way to do it, that doesn't answer the question:
        egrep -v 'a' filename
    Without using the -v option:
        egrep '^[^a]*$' filename
    The pattern [^a]* matches all strings with no a's. The ^ at the beginning 
    and the $ at the end specify that the entire line must be such a string.
    Without these, [^a]* matches every line, since it include the strings of 
    length 0.

 2. egrep -v '\.' filename

    The backslash is needed to 'quote' the period.

 3. '\$([0-9])+(\.[0-9][0-9])?'

    Dollar sign, followed by one or more digits, followed (optionally)
    by a period and two digits.

 4. The following commands are the tail end of a 30-second sequence of
    commands used to find this out.

      % egrep 'oo' /usr/dict/words | egrep '.............'
      bootstrapping
      schoolgirlish
      schoolteacher
      tablespoonful
      % egrep 'ee' /usr/dict/words | egrep '.............'
      committeewoman
      committeewomen


 5. (a)  State transitions: 0 -> 0 -> 0 -> 1 -> 1 -> 1.

    (b)  State transitions: 0 -> 0 -> 1 -> 1 -> 3 -> 3.

    (c)  All binary strings with exactly two 1s.

    (d)  0*10*10*
         

 6.



 7.



 8.   State i represents bitstrings whose remainder is i upon division by 4.





 9. (a) Binary strings ending in 0 with no two consecutive 1's or
        the empty string.

    (b) (0 | 10)*