This is an in-class group exercise. orm groups of 2 to 4. Solve the following problem as a group. Write down your answers and be prepared to share with the class. You have about 20 minutes.

(I used this exercise on the last day of class to ensure students got practice with problems that might appear on the final exam.)

1. How many strings are represented by the following grammar?
   a ( b | c ) (( d | e | f ) g | h )
2. (9.5, question 5) Answer the following five questions with the grammar:

   val ::= number | val pair
   number ::= digit+
   pair ::= number op | number pair op
   op ::= "+" | "-" | "*" | "/"
   digit ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
   

   1. Give test strings that satisfy Terminal Symbol Coverage (TSC)
   2. Give test strings that satisfy Production Coverage (PC)
   3. Which of the following strings can be generated by the (unmutated) grammar?

      42 
      4 2 
      4 + 2 
      4 2 + 
      4 2 7 - * 
      4 2 - 7 * 
      4 2 - 7 * + 
      

   4. Now consider this mutation of the grammar:

      pair ::= number op | number pair op | op number

      Find a string that is generated by the mutated grammar, but not by the original grammar.
   5. (Challenging) Find a string whose generation uses the new rule in the mutant grammar, but is also in the original grammar. Demonstrate your answer by giving the two relevant derivations.
3. Consider the following XML schema for a USA zip code:

   <?xml version="1.0" ?> 
   <xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema">
   
       <xsd:simpleType name='zipcode'>
         <xsd:restriction base='xsd:string'>
           <xsd:pattern value='[0-9]{5}(-[0-9]{4})?'/>
         </xsd:restriction>
       </xsd:simpleType>
   </xsd:schema>
    

   1. Write two test strings of different lengths that satisfy the schema, and two strings that do not satisfy the schema.
      
      
   2. All zip codes in Virginia, DC, and Maryland must begin with 2. Change the schema’s pattern to only allow zip codes from that area.