CSC 341 (Fall 2021)

Lab: Nondeterminism

Problem 1: Interpretation

Example NFAs
  1. Determine whether the strings:

    • \(101\)
    • \(0111\)
    • \(1010\)
    • \(\epsilon\)

    Are accepted by the NFAs above.

  2. Give a formal description of the languages that each of the NFAs above recognize.

Problem 2: Nondeterministic Design Patterns

Construct an NFA that productively takes advantage of nondeterminism to recognize each of the following languages. In the following languages, \(\Sigma = \{\, 0, 1 \,\}\).

Problem 3: Infinite Nicolas Cages?

Consider the following partial NFA that features an “epsilon loop.” The remainder of the NFA does some computation on \(q_0\) which is irrelevant for our purposes.

  ┌───ϵ───┐
  ↓       │
→ q0 -ϵ→ q1
  │
  └── ⋯

And consider the following critique of this construction:

This NFA is impossible! The epsilon loop will spawn an infinite number of threads of execution!

Explain in a few sentences why such a situation is “ok” by appealing to the formal definitions of a NFA.

(Hint: do the definitions prescribe how we should execute a NFA?)