The emptiness problem for 1-way probabilistic finite state automata is undecidable. (See Condon Lipton Frievalds (sp?).)
Swapnil Bhatia
- 313
- 2
- 12