We have discussed DFA:s, i.e., Discrete Finite Automata, and their use in efficient matching of languages. You

have also seen them in previous modules.

You will also have previously encountered NFA:s, i.e., Non-deterministic Finite Automata. (One way to briefly

define them is that they are automata where you sometimes have to make a choice between which of several

possible transitions to follow for an input character.)

What is true about the relative power of DFA:s and NFA:s?

Select one:

O a. Anything that can be matched by an NFA can also be matched by a DFA

O b. There are problems (formally: languages) that can be expressed via NFA:s that can't be expressed via DFA:s.