Problem 3; 2-Jun-2000

XML: Foundations, Techniques, Applications; Summer 2000

Harold Boley; DFKI, Univ. Kaiserslautern


The extended BNF or DTD meta-syntax "|" and "?" (respectively "+" and "*") permits to abbreviate a finite (respectively infinite) set of allowed DTDs into a single one. Analogously, for the corresponding document type trees (DTTs). For example, the - incomplete - extended DTT/DTD
      x                                     <!ELEMENT x       (y | z) >
     * *
    *   *
   *******
  *       *
 *         *
y           z
abbreviates a set of two (rather degenerate) simple DTTs/DTDs
        x            x                    { <!ELEMENT x       (y) > ,
       /              \                     <!ELEMENT x       (z) >  }
      /                \
     /                  \
    /                    \
   /                      \
{ y            ,           z }

Now, consider the following - complete - extended DTD:

<!ELEMENT sentence (article, (goodnoun | badnoun), (goodverb | badverb), adverb? >
<!ELEMENT article  (#PCDATA) >
<!ELEMENT goodnoun (#PCDATA) >
<!ELEMENT badnoun  (#PCDATA) >
<!ELEMENT goodverb (#PCDATA) >
<!ELEMENT badverb  (#PCDATA) >
<!ELEMENT adverb   (#PCDATA) >

a) Give the corresponding DTT.

b) Write an XML element that is valid w.r.t. this DTD/DTT.

c) What is the cardinality of the set of simple DTDs/DTTs abbreviated by this extended meta-syntax DTD/DTT?

d) Can you add some "+" or "*" meta-syntax and tell the cardinality of your new simple-DTD/DTT set?