Exercise 2        Name __________________        Score __/31

1. (10) Write regular expressions for the following:
   1. Strings over the alphabet {a,b,c} where the first a precedes the first b.
      
      c*a[ac]*b[abc]* assumes at least one a and one b
       
   2. Strings over the alphabet {a,b,c} with an even number of of a's.
      
      (aa|b|c)* since 0 is even
       
   3. Binary numbers that are multiples of four.
      
      That means 0, 000000, 0100, 1000, 00001100, 000000010000, 00000000010100, ...
      
      0*[01]*00 | 0⁺
       
   4. Strings over the alphabet {a,b,c} that don't contain the contiguous substring baa.
      
      Consider comments of the form // any character \n
                   //^(\n)\n
      
      Consider comments of the form ## any characters including # except ## ##
      
                   ##((#|)^(#))*##
      
      One correct answer was very close to Jordan's. The grep regular expression reading from file test.txt of:
      
          grep32 /E4 "([ac]*b(c|a[^a])[ac]*b*)+|[ac]+" test.txt
      
      rejects: ccccaababcacabaaccca
      accepts: ccccaababcacabacccab
      accepts: ccccaaacacaaccca
       
   5. The language of non-negative integer constants in C, where numbers beginning with O are octal constants and other numbers are decimal constants.
      
      O[0-7]+ | [0-9]+
      
       
2. (1) Why are you not surprised that there is no regular expression defining strings of a's and b's  that are palindromes (the same forward as backward). Hint: Consider the number of finite-automata states required.
   
   Requires an infinite number of states: a, aa, aba, abba, ... because two ends about a center point must be equal. Can only specify by listing each case.
    
3. (4) Explain in informal English what each of these finite-state automata recognizes.
   
   a.    State 9 should be final is 0110
          State 10 is 1xxx, 00xx, 010x or 0111 where x =0|1
   b.    a or 5n+1 a's for n=1 to infinity
    
4. (4) Convert these regular expressions to NFA.
   1. (if|then|else)
      
      
       
   2. (a((b|a)*c)x)*|x*a
      
      

    

5. (12) Convert these NFAs to DFAs, just do a.
   

a.

trans 0 1 2 3 x 0 2 0 0 y 0 3 0 0 z 0 0 1 0

            1              = {1,2,3,4} = state[1]
           {1,2,3,4}_x = {5,6,7}    = state[2]
           {1,2,3,4}_y = {6,7}       = state[3]
           {5,6,7}_z    = {1,2,3,4}  = state[1]