• To: Gustaf Liljegren <gustaf.liljegren@b...>
• Subject: Re: Non-deterministic content models
• From: ht@c... (Henry S. Thompson)
• Date: Thu, 17 Jul 2003 18:51:45 +0100
• Cc: xml-dev@l...
• In-reply-to: <3.0.6.32.20030715055242.01069350@p...> (GustafLiljegren's message of "Tue, 15 Jul 2003 05:52:42 +0200")
• References: <3.0.6.32.20030715055242.01069350@p...>
• User-agent: Gnus/5.1002 (Gnus v5.10.2) XEmacs/21.4 (Portable Code, linux)

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?

ht
-- 
  Henry S. Thompson, HCRC Language Technology Group, University of Edinburgh
                      Half-time member of W3C Team
     2 Buccleuch Place, Edinburgh EH8 9LW, SCOTLAND -- (44) 131 650-4440
	    Fax: (44) 131 650-4587, e-mail: ht@c...
		     URL: http://www.ltg.ed.ac.uk/~ht/
 [mail really from me _always_ has this .sig -- mail without it is forged spam]

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

• References:
  • Non-deterministic content models
    • From: Gustaf Liljegren <gustaf.liljegren@b...>

• Prev by Date: Re: Who provide for the syntax for "file:///c:/" ?
• Next by Date: Fwd: RE: Fwd: RFC 3548 on The Base16, Base32, and Base64 Data Encodings
• Previous by thread: Re: Non-deterministic content models
• Next by thread: Re: Non-deterministic content models
• Index(es):
  • Date
  • Thread