[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: Non-deterministic content model
- From: Murali Mani <mani@CS.UCLA.EDU>
- To: Derek Denny-Brown <email@example.com>
- Date: Wed, 13 Jun 2001 12:15:38 -0700 (PDT)
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.