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

Re: Non-deterministic content models

• To: "Gustaf Liljegren" <gustaf.liljegren@b...>,"Henry S. Thompson" <ht@c...>
• Subject: Re: Non-deterministic content models
• From: "Bob Foster" <bob@o...>
• Date: Thu, 17 Jul 2003 19:07:01 -0500
• Cc: <xml-dev@l...>
• References: <3.0.6.32.20030715055242.01069350@p...> <f5bn0fdf3da.fsf@e...>

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

• Follow-Ups:
  • Re: Non-deterministic content models
    • From: Murali Mani <mani@C...>

• References:
  • Non-deterministic content models
    • From: Gustaf Liljegren <gustaf.liljegren@b...>
  • Re: Non-deterministic content models
    • From: ht@c... (Henry S. Thompson)

• Prev by Date: RE: Defining non-WXS datatypes
• Next by Date: Re: Non-deterministic content models
• Previous by thread: Re: Non-deterministic content models
• Next by thread: Re: Non-deterministic content models
• Index(es):
  • Date
  • Thread