[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: Non-deterministic content model
- From: Jason Chalecki <jchaleck@microsoft.com>
- To: Murali Mani <mani@CS.UCLA.EDU>, "K.Kawaguchi" <kohsukekawaguchi@yahoo.com>
- Date: Wed, 13 Jun 2001 14:07:48 -0700
((a, b)*, a) essentially represents the language where the first and
last letter is a. Additionally, if there are b's, a and b must
alternate. So (a, (b, a)*) matches the same language and is
deterministic, correct?
However, this is a specific solution and not a general algorithm to
transform non-deterministic to deterministic.
Jason
-----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
>
------------------------------------------------------------------
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