[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Non-deterministic content models

• To: Bob Foster <bob@o...>
• Subject: Re: Non-deterministic content models
• From: Murali Mani <mani@C...>
• Date: Thu, 17 Jul 2003 16:56:14 -0700 (PDT)
• Cc: <xml-dev@l...>
• In-reply-to: <009401c34cc0$84cd8880$1401a8c0@snobird>

I think we should say a regular expression cannot be converted into
1-unambiguous regular expression.. cheers and regards - murali.

On Thu, 17 Jul 2003, Bob Foster wrote:

> From: "Henry S. Thompson" <ht@c...>
> > Any non-deterministic finite-state automata can be determinized.
> >
> > Some non-deterministic regular expressions _cannot_ be determinized.
> >
> > A common example of a non-determinizable regexp is the one for chess
> > games:
> >
> > w(bw)*b?
>
> I'm getting that "jargon soup" feeling. When you talk about "determinizing"
> an NFA, I guess you mean converting it to a DFA.
>
> But when you talk about "determinizing" a regular expression, I guess you
> mean converting it to a deterministic regular expression.
>
> No relationship between these two operatons.
>
> Bob Foster
>
>
> -----------------------------------------------------------------
> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
> initiative of OASIS <http://www.oasis-open.org>
>
> The list archives are at http://lists.xml.org/archives/xml-dev/
>
> To subscribe or unsubscribe from this list use the subscription
> manager: <http://lists.xml.org/ob/adm.pl>
>

• References:
  • Re: Non-deterministic content models
    • From: "Bob Foster" <bob@o...>

• Prev by Date: Re: Non-deterministic content models
• Next by Date: Re: Defining non-WXS datatypes
• Previous by thread: Re: Non-deterministic content models
• Next by thread: Why 3D Redux? (RE: [OT] Tim Bray on Slashdot)
• Index(es):
  • Date
  • Thread