[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: Non-deterministic content model
- From: Derek Denny-Brown <derekdb@microsoft.com>
- To: Murali Mani <mani@CS.UCLA.EDU>, "K.Kawaguchi" <kohsukekawaguchi@yahoo.com>
- Date: Wed, 13 Jun 2001 14:04:00 -0700
> 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
> >
>
>