RE: Non-deterministic content model

[Murali Mani <mani@CS.UCLA.EDU>]

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.
>