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.


    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

  5. 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) "><"

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

    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.