[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] RE: Non-deterministic content model
Oops, I think i should change my first example to (a & b?) -- rather -- (a, b? | b?, a) I think the above *cannot* be written as a 1-unambiguous regular expression -- this is given in Anne's thesis referred in the XML 1.0 recommendation -- please double check... i am saying offhand.. but the conclusions are true, i believe... thanks for pointing it out.. regards - murali. On Wed, 13 Jun 2001, Murali Mani wrote: > > Derek, I am sorry I would like to say that the following statement is > *not* true to the best of my knowledge -- > > "Every non-deterministic content model can be written as a deterministic > content model" > > shall I say the above is also called 1-unambiguous content models studied > by Anne-Bruggemann Klein in her thesis. > > I would also like to re-introduce the term model group -- a model group > has lot of operators, a regular expression is also a model group -- it > used only the operators -- *, | (choice), and , (concatenation). > > Consider regular expressions -- the regular expression (a, b | b, a) can > *never* be written as a 1-unambiguous regular expression -- it can however > be written as (a & b) -- when it will be 1-unambiguous. > > Consider another regular expression -- (a*, b*, a*) -- it is ambiguous, > and it has no 1-unambiguous content model (consider any of the existing > operators) -- (actually please double check this example -- i am quite > sure it is not 1-unambiguous). > > Note -- Anne's thesis includes a portion where given a regular language, > she identifies whether there is a 1-unambiguous regular expression for it. > > she leaves it as an open problem: given a regular language, whether there > is a 1-unambiguoud model group (with the SGML DTD operator & in addition > to the regular expression operators). > > In short, i think there exist inherently 1-ambiguous regular languages. > > <warning>speaking for himself only</warning> > > cheers and regards - murali. >
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|