READING for Week 7


Sedgewick, 108-114

Kernighan and Ritchie, 104-107

---------------------------------------------

			 EXERCISES for Week 7

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

 2. Give a grep 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. Draw a finite-state automaton that accepts all strings that contain
    three consecutive A's.

 6. If the machine drawn below is started at state 0 with the input 00100,
    what state is it in when it stops?











 7. If the machine of question 6 is started at state 0 with the input 01010,
    what state is it in when it stops?

 8. Describe the language accepted by the finite-state automaton of question 6.

 9. Draw a finite-state automaton that accepts all strings of 0s and 1s
    that represent a binary number that is divisible by 4.

10. Describe the language accepted by the finite-state automaton with the
    following state-transition table.

            0  1
         -------
         0  3  1
         1  3  2
         2  2  2
         3  3  1

11. Give a regular expression that describes the language accepted by
    the machine of question 7.








                    Answers to Exercises for Week 7

 1. Easy way to do it, that doesn't answer the question:
        grep -v a filename
    Without using the -v option:
        grep '^[^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. grep -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.

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

 5.







 6. State transtions: 0 -> 0 -> 0 -> 1 -> 1 -> 1.

 7. State transtions: 0 -> 0 -> 1 -> 1 -> 3 -> 3.

 8. All binary strings with exactly two 1s.

 9.







10. Binary strings ending in 0 with no two consecutive 1s.


11. (0 + 10)(0* + (10)*)*