Homework 2: Due February 9, 2011

1. a) Write BNF grammar rules for a language with alphabet { a, b } where all strings contain at least two a's. For example, aa, aaab, baa, abba are all sentences in the language.
   
   b) Draw an finite state automata which recognizes the sentences in this language.
   

2. Write BNF grammar rules for a language consisting of all strings from the alphabet { X, Y, Z } such that there are exactly the same number of X's and Y's in every string.

   Examples:

   Valid Strings:    XYZXYXY     XXYXYYYX     ZZ     ZYZYZZXYZZXZZXZ
   
   Invalid Strings:     XZ     XYXYZY

3. Use the following Ada syntax diagrams to determine which of the following are valid numeric_literals. Assume normal definitions of digit.

 

















 

a)   123.4E-38

b)   9_9_9_9_9

c)   987.

d)   16#ABC.62#

e)   2#1100#E4

f)   600E8.0

4. Which of the following are valid according to the production [10] AttValue?
   ( See the XML specification at the W3 Consortium here: http://www.w3.org/TR/REC-xml.. You may need to refer to additional productions to answer this question.)
   
   a) "wxyz"
   b) 'abc'
   c) "R&R"
   d) ''        (that's two single-quotes with nothing between them)
   e) "abc&de::f;&_x_;"
   f) "><"

5. a) Write an XML DTD for people as described below:

   • A person has name, age, and children elements. The children element is optional.
   • The name element has a firstname element followed by either a middlename or initial element, followed by a lastname element. The middlename or initial is optional.
   • The children element consists of 0 or more persons.
   • All of the remaining elements are character data.

   b) Create an example XML document which includes all combinations of elements for the DTD given in part a).

    You should view the XML document in a web browser and also validate your XML document. One online validation site is: http://www.w3schools.com/xml/xml_validator.asp

   Put the DTD and XML files in a zip file and SUBMIT HERE.