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:
URL: http://www.ltg.ed.ac.uk/~ht/
[mail really from me _always_ has this .sig -- mail without it is forged spam]
