CSC 341 (Fall 2021)

Reading: Nondeterminism


Next, we explore an interesting extension of finite automata, nondeterminism, which allows a machine to search multiple possible acceptance paths in parallel. Nondeterminism has a number of interesting, subtle properties that we’ll spend class grasping with the help of Nicolas Cage.

Sipser Reading

Through section 1.2 (Nondeterminism), stopping at “Equivalence of NFAs and DFAs.”

Reading Problem (Compare and Contrast): list the differences in the formal definition of a deterministic finite automata and a nondeterministic finite automata. Make sure to note not just the differences in the tuple of each machine’s components but also the differences in the acceptance conditions of the two models.