# Non-Determinism and Underspecification

**Underspecified command** is command that gives one result, but program semantics does not say which one.

- Example: parameter order in C compilers is underspecified
- user cannot assume that parameters are evaluated e.g. left-to-right

In contrast, we now consider **non-deterministic commands** that simultaneously yields **multiple results**

- typically, if there exists a choice for which program gives correct result, the language implementation should find it

Languages with non-deterministic commands to more elegantly express **search algorithms**

This is like **non-deterministic automaton**, but we user it for arbitrary programs, not just finite-state machines

**Note:** subset construction still works - we could be computing sets of results

- but storing sets of states is expensive
- many implementations are instead based on back-tracking

Applications:

- easier programming of difficult problems (deciphering, natural language processing, scheduling)
- program testing: searching for error in programs