Sure. As long as each response is deterministic, several states might go to the same state on the same next input. Since you can only be in one of the states, determinism isn't lost.
x
A ----> B
| |
|y |z
| |
V z V
C ----> D