COS 126: Fall 1996 Exercise Set 10

Answers

These exercises are intended help review the material on finite state automata. Do not turn in solutions.

1. Give an egrep pattern that matches all lines that contain no a's.
2. Give an egrep pattern that matches all lines that do not contain two consecutive a's.
3. Give an egrep pattern that matches all lines that do not contain three consecutive a's.
4. Give an egrep command that prints lines that contain no periods.
5. Give an egrep pattern that matches all lines containing dollar amounts. (Examples: $12.34 or $500.00 or $1000).
6. Find the longest word in /usr/dict/words that contains a double vowel (aa, ee, ii, oo, or uu).
7. Draw a finite state automaton that accepts all strings that contain three consecutive A's.
8. If the machine drawn below is started at state 0 with the input 00100, what state is it in when it stops?
   
9. If the machine in the previous question is started at state 0 with the input 01010, what state is it in when it stops?
10. Describe the language accepted by the finite state machine used in the previous two questions.
11. Draw a finite state automaton that accepts all strings of 0s and 1s that represent a binary number that is divisible by 4.
12. Draw a finite state automaton that accepts all strings of 0s and 1s that represent a binary number that is divisible by 3.
13. Describe the language accepted by the finite state machine with the following state transition table.

       0   1   Final?
    0  3   1
    1  3   2
    2  2   2
    3  3   1    Yes

14. Give a regular expression that describes the language accepted by the machine in the previous question.

Answers

As always, try to solve the problems before looking at the suggested solutions.

1. An easy way to do it, but that doesn't answer the question: egrep -v a
   Without using the -v option: egrep '^[^a]*$'
   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, because it matches strings of length 0.
2. egrep '^a$ | ^(a?[^a]+)*$'
   Every line consists of arbitrary sequences of non-a's, separated by single a's. The ? (0 or 1 a's) generalizes the pattern, in the sense that there are more ways to match it, but it is included only to avoid specifying that the line must begin with an a.
3. egrep '^aa?$ | ^(a?a?[^a]+)*$'
4. egrep -v '\.'
   The backslash is needed to "quote" the period.
5. egrep '\$([0-9])+(\.[0-9][0-9])?'
   Dollar sign, followed by one or more digits, followed (optionally) by a period and two digits.
6. The following commands print, respectively, 15-letter and 14-letter words that have doubled vowels.

   % egrep 'aa|ee|ii|oo|uu' < /usr/dict/words | egrep '...............' 
   % egrep 'aa|ee|ii|oo|uu' < /usr/dict/words | egrep '..............'
   committeewoman
   committeewomen

7. 
8. State transtions: 0 0 0 1 1 1.
9. State transtions: 0 0 1 1 3 3.
10. All binary strings with exactly two 1s.
11. Ends in two 0s.
12. Try it!
13. Binary strings ending in 0 with no two consecutive 1s.
14. (0 + 10)(0* + (10)*)*