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