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)*