RE/FSA EXERCISES




 1. Give an egrep pattern that matches all lines that contain no a's.

 2. Give an egrep command that prints out all lines that contain no periods.

 3. Give an egrep pattern that matches all lines containing dollar amounts
    (examples: $12.34 or $500.00 or $1000).

 4. Find the longest word in /usr/dict/words that contains a double vowel
    (aa, ee, ii, oo, or uu).

 5. Consider the FSA below.
(a) If the machine is started at state 0 with the input 00100, what state is it in when it stops? (b) If the machine is started at state 0 with the input 01010, what state is it in when it stops? (c) Describe the language accepted by the FSA. (d) Give a regular expression that matches the same language. 6. Draw a finite-state automaton that accepts all strings that contain three consecutive a's. 7. Draw a finite-state automaton that accepts all strings of 0's and 1's that ends in two 0's. 8. Draw a finite-state automaton that accepts all strings of 0's and 1's that represent a binary number that is divisible by 4. 9. (a) Describe the language accepted by the following FSA.
(b) Give a regular expression that describes the language accepted by the machine.