# WIP: Finite automata

ðŸš§ UNDER CONSTRUCTION ðŸš§

Caution: this section is a work in progress

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**.

ðŸ’¡ DEFINITION

A **deterministic finite automaton** is a restricted deterministic Turing machine that: never writes to the tape and moves the read head one space to the right on each transition.

- Never writes to the tape.
- Moves the read head one space to the right on each transition.

A deterministic finite automaton is abbreviated as **dfa**.

ðŸ‘€ 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}

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:

ðŸ’¡ DEFINITION

A **nondeterministic finite automaton** is just like a deterministic finite automaton, except it can contain:

- Ambiguous transitions, where multiple transitions out of the same state can match the same symbol.
- \(\epsilon\)-transitions, which match any character and do
*not*move the read head to the right.

A nondeterministic finite automaton is abbreviated as **nfa**.

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

ðŸ‘€ EXAMPLE

Try out this nfa:

Alphabet is: {G}

What strings does this nfa accept?

## Reveal answer

This nfa accepts strings of `G`

s 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

ðŸš§ UNDER CONSTRUCTION ðŸš§

Caution: this section is a work in progress

## Regular languages

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

ðŸ’¡ DEFINITION

A language is **regular** if it can be accepted by a deterministic finite automaton, or any equally powerful machine (such as nondeterministic finite automata and regular expressions).