Reading:

• Lectures 7, 8, and 9 of Automata and Computability
• Various in Chapters 7, 8, and 9 of Learning Perl, Third Edition

Total Points: 130

Purpose: Practice with regular languages.

Problem 3.0 [10 points]

nullstring < a < b < aa < ab < ba < bb < aaa < aab < ...

1. ab+aab
2. b*(ab)*a*
3. (a*+b*)(a*+b*)(a*+b*)
4. a*(baa*)*b*
5. b*(a+ba)*b*

Problem 3.1 [10 points]

Problem 3.2 [15 points]

Problem 3.3 [10 points]

Problem 3.4 [10 points]

Problem 3.5 [10 points]

Problem 3.6 [10 points]

1. Miscellaneous Exercise 15, page 320 of Automata and Computability.
2. Miscellaneous Exercise 17, page 321 of Automata and Computability.

Problem 3.7 [10 points]

Problem 3.8 [20 points]

1. a a* = a* a
2. (aa*bb*)* = e + a(a+b)*b, where e denotes the empty string
3. (aa*b)*b = b + a(a+ba)* bb
4. a(ba)* = (ab)*a

Problem 3.9 [25 points]

1. Write perl regexes for the languages in Problem 3.2. You may test them against the file bin16.dat, which should contain all binary strings of length less than or equal to 16. For uniformity, use the string constant $S="[01]". Only turn in the regexes themselves (everything between and including the /'s) plus a record of the number of members of bin16.dat matching each. Note: For this part, do not use any special operators in perl beyond regular expression analogues, character classes, and anchoring. Specifically, do not use perl's negation operator (or test "not true").

2. Write perl regexes for the following subsets of {a,b,c,...,z}*, assuming the vowels are {a,e,i,o,u}.
   1. All words that end in dous
   2. All words that have only one vowel
   3. All words that have alternating consonants and vowels
   4. All words that have four or more consecutive consonants
   5. Repeat ii-iv above (as ii'-iv'), assuming y is also a vowel
   In each case, test your program(s) versus words.dat, which is a copy of /usr/dict/words from my Unix machine. As for code, turn in the regexes themselves, plus any string constants you may have defined. For part i, also report all matching words. For parts ii and ii', iii and ii', also report only the longest words which match the pattern. For parts iv and iv', also report only the shortest words which match the pattern.

   You may find it useful to examine the following Perl code:

   ###############################
   # SUBROUTINE to print the longest word(s) in a list
   #   Invoked: print_longest (@list)
   ###############################
   sub print_longest {
     my @list;
   
     @list=sort by_length @_;
     $last=pop(@list);
     print $last;
     $l=length($last);
     while (length($last=pop(@list))==$l) {
       print $last;
     }
   }
   
   # auxiliary subroutine for sorting
   # cf. pp. 156-9 of _Learning_Perl_ (pp. 213-9 of 3rd ed.)
   sub by_length {
     length($a) <=> length($b);
   }