RE: Non-deterministic content model

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

Ok, thanks, let me correct it once more.. (hopefully for the last time) --

Kohsuke original one was

(a, b)*, a?

I would now make it a? rather than a -- now, how does it look??

Yes, you are again right about the language defined by ((a, b)*, a) being
1-unambiguous -- your regular expression is the proof..

On Wed, 13 Jun 2001, Derek Denny-Brown wrote:

> > Also I think, the language specified by ((a, b)*, a) cannot
> > be written as
> > an 1-unambiguous regular expression or 1-unambiguous model group -- I
> > think --
>
> (a, (b,a)*)
>
> It is not an 1-unambiguous model group (I think), but it is an
> 1-unambiguous regular expression (I'm sure).
>
> Orignal RegExp -> NDFA
> 0	a:1 a:2
> 1	b:0
> 2	$
>
> DFA
> 0' (0)	a:1'
> 1' (1,2)	b:1' $
>
>
> Derek Denny-Brown
>
>
>
> > -----Original Message-----
> > From: Murali Mani [mailto:mani@CS.UCLA.EDU]
> > Sent: Wednesday, June 13, 2001 1:36 PM
> > To: K.Kawaguchi
> > Cc: Derek Denny-Brown; Steve Rosenberry; xml-dev@lists.xml.org
> > Subject: Re: Non-deterministic content model
> >
> >
> >
> > Actually Kohsuke is right -- (a & b?) is *not* inherently 1-ambiguous.
> >
> > Also I think, the language specified by ((a, b)*, a) cannot
> > be written as
> > an 1-unambiguous regular expression or 1-unambiguous model group -- I
> > think --
> >
> > when you see an "a" in the string, you do *not* know whether it is the
> > first a or the second a, unless you know whether there is b following
> > it.
> >
> > i think the above example holds for all model groups defined
> > to date --
> > thanks a lot.
> >
> > are there any opinions/suggestions??
> >
> > Derek, try to give the content model for ((a, b)*, a), if you are not
> > convinced.
> >
> > thanks and regards - murali.
> >
> > On Wed, 13 Jun 2001, K.Kawaguchi wrote:
> >
> > >
> > > > (a, b? | b?, a)
> > >
> > > Since the above is the equivalent of ( a | ab | ba ),
> > > you can write it as
> > >
> > > (a,b?) | (b,a)
> > >
> > > which is deterministic.
> > >
> > > How about this?
> > >
> > > > (a b)* a?
> > >
> > >
> > > I think this cannot be written by the deterministic content model.
> > >
> > > regards,
> > > ----------------------
> > > K.Kawaguchi
> > > E-Mail: kohsukekawaguchi@yahoo.com
> > >
> > >
> > > ------------------------------------------------------------------
> > > The xml-dev list is sponsored by XML.org, an initiative of OASIS
> > > <http://www.oasis-open.org>
> > >
> > > The list archives are at http://lists.xml.org/archives/xml-dev/
> > >
> > > To unsubscribe from this elist send a message with the single word
> > > "unsubscribe" in the body to: xml-dev-request@lists.xml.org
> > >
> >
> >
>