Non-determinstic finite automata (NFAs)
===

Non-determinstic automata were introduced by [Rabin and Scott](https://www.researchgate.net/publication/230876408_Finite_Automata_and_Their_Decision_Problems) in 1959. Both authors made much deeper contributions to computer science (such as zero knowledge proofs and domain theory), but non-determinstic automata were important enough to grant them the "Nobel price of computer science", the Turing award in 1976.

Most algorithms are deterministic and, until not so long ago, implementations on a modern computer were deterministic (even those using random numbers). So why are non-determinstic machines so important?

- Specifications as opposed to implentations typically do not determine computations completely.
- Modelling open systems, the environment is often best modelled non-determinstically. For example,
- an operating system interacting with a keyboard cannot predict which keys will be pressed next
- in security modelling an attacker must allow the intruder any possible action
- In the presence of concurrency or parallelism, the precise timing or even order of actions is not determined.
- In algorithms, non-deterministic machines are crucial to describe the possibly most important class of algorithms, namely those in non-deterministic polynomial time (NP).
- Non-deterministic automata and deterministic automata are equivalent, but non-determinstic automata can be exponentially smaller.

Let me know if you can think of reasons to extend this list ...

## Aim

To understand the following:

- How to convert a non-deterministic finite automaton (NFA) into an equivalent deterministic finite automaton (DFA).

- Two automata are equivalent if they accept the same language.

- An NFA accepts a word $w$ if there is some path labelled $w$ leading from the initial state to some final state.

## Required reading

Required reading is from Section 2.3 of the automata theory book, in particular

- Sections 2.3.2-2.3.5
- Definition of an NFA on page 57
- Definition of the language of an NFA on page 59
- The subset or powerset construction on page 61
- Exercises 2.3.1 and 2.3.2

## Examples

How do we find finite determinstic finite automata that accept the following languages? How do we do this in a systematic way that works for all examples of this kind and can be implemented in a uniform fashion?

We explained the construction of a DFA from an NFA with Figure 2.9 of Example 2.6 on page 56 of the book where the alphabet is $\Sigma=\{0,1\}$ and the language is

the set of strings ending in "01"

(See Figure 2.12 on page 61 of the book for a solution. Note that Figure 2.12 contains all subsets of states, but that only three of them are reachable from the initial state. This is the reason that we can get away with a smaller automaton, see Figure 2.14 on page 63.)

## Homework

**Mandatory:**

- Required reading, see above. Post any questions, comments, etc on this material as an answer to my homwork question. Apply the subset construction from the lecture (or the book) to turn them into DFAs.

- Take [these NFAs](https://github.com/alexhkurz/compiler-construction-2021/blob/master/Sources/nfas-assignment1.pdf) that specify the languages for Assignment 1.
- For Question 1, notice how much simpler the NFA is than the equivalent DFA.
- For Question 2, I would expect that the subset construction will give a larger automaton then then you are using for the assignment. This is fine, there is a separate procedure for minimizing automata.
- For Question 3, do you get the same DFA as you used in Assignment 1.

- Exercise 2.3.1 of the book.

**Optional:** Exercises 2.3.2 to 2.3.7 of the book.