Computational nut?

[Soren Kuula]

Hi,

For those of you who like something to think about:

If I give you a DTD, can you (tell me how to) return to me a regular
language over elements on document order in documents that are valid
wrt. the schema?

Ex.:

<!ELEMENT a (b|c)>
<!ELEMENT b (d*)>
<!ELEMENT c(b)>

A valid document

<a>
<b>
<d/> <d/>
</b>
</a>

Parser's document order start tag encounters: a b d d

A regex (just hand made) that should work: a ( (b d*) | ( c b d* ) )

Now generalize

Or maybe I'm stupid; is it regular at all -- generally? With cycles in
the schema (x may contain x, and also y, which may contain x ... etc)



My only observation is that descendants go before siblings.

Soren

 

[Soren Kuula]

Hi,

My only observation is that descendants go before siblings.

and that regular languages over regular languages are still regular?

Soren