WIP: Finite automata

Until this point, we've worked with computational models such as Turing machines and SISO Python programs that have the power to solve a wide variety of problems. With that power comes a downside: we can no longer guarantee that programs for these computational models terminate, or even ensure they have some desired behavior. Can we get away with less power that lets us still solve a useful class of problems?

Finite automata

In fact, there are multiple such models! Together, these models form a hierarchy of increasingly more powerful computational models, culminating with Turing machines and equivalent models. The first, and the least powerful, computational model we'll look at is the finite automaton.

👀 EXAMPLE

Here's a dfa. Each transition is labelled with all the symbols that match that transition. Remember, each transition matches a symbol and implicitly moves the read head to the right by one cell. Try some input strings to see if you can figure out what this dfa does:

Alphabet is: {A, C, G, T}

Input should be surrounded by double quotes

Have you figured out what strings this dfa accepts?

Reveal answer

This dfa accepts any string that contains GAGA inside of it.

Dfas can be encoded as strings in the same way as any Turing machine. In fact, the encoding is more shorter because the transitions are simpler, with the read head behavior not needing to be explicitly specified. After all, the read head behavior is always the same: move one cell to the right. Similarly, there's no need to specify what to write to the tape, because dfas can't write to the tape at all.

👀 EXAMPLE

How might you encode this dfa as a string, based on the usual string encoding for Turing machines?

Reveal answer

"q0->q0: ACT
 q0->q1: G
 q1->q0: CT
 q1->q1: G
 q1->q2: A
 q2->q0: ACT
 q2->q3: G
 q3->q0: CT
 q3->q1: G
 q3->qA: A"

Just like Turing machines can be nondeterministic, so can finite automata:

Nfas are to dfas as nondeterministic Turing machines are to deterministic Turing machines.

👀 EXAMPLE

Try out this nfa:

Alphabet is: {G}

Input should be surrounded by double quotes

What strings does this nfa accept?

Reveal answer

This nfa accepts strings of Gs whose length is a multiple of two or three (or both!).

WIP: we will show that nfas are equivalent in power to dfas.

Regular expressions

Regular languages

With these computational models in place, we can classify languages into a new category: