# Deterministic Finite Automaton (DFA)

A DFA is a directed graph whose nodes are called **states** and whose edges are called **transitions**.

In the context of studying Formal Languages in Formal Languages in CS241E, I lerned to use DFAs to do 2 things:

- Solve the
**recognition**problem: given a word $w$, is $w$ in the specified language $L$? [[notes/Deterministic Finite Automaton#Recognition|Deterministic Finite Automaton#Recognition]] - Implement Scanning for a Regular Language

Personal Note*: I feel like the above is really similar to the notation I have seen for a Markov Decision Process.

We can define the extended transition function $δ_{∗}:Q×∑_{∗}→Q,w$ which maps a state $q$ and a sequence of symbols $w$ to a new state $q_{0}$ as follows: $δ_{∗}(q,ε)=q(ϵ=empty word)$ $δ_{∗}(q,first::rest)=δ_{∗}(δ(q,first),rest)$

The following diagram shows an example of a DFA over the alphabet $∑={a,b}$ that specifies the language of words that contain an odd number of $a$’s (and any number of $b$’s’):

- The double circles means an accepting state

If there is no transition labelled with the symbol, the DFA is said to get stuck and the word is not in the language.

- Serendipity, this reminds me of ideas for Serendipity, this reminds me of ideas for Backup Diagrams??

We can make transitions through the DFA on a sequence of symbols rather than only a single symbol at a time, we say that the DFA accepts a word $w$ if $δ_{∗}(q_{0},w)∈A$.

Example of a DFA for detecting if an input string is not divisible by 3. This is actually a really clever idea that Chester Chung gave me

### Recognition

Recognition is the process of determining if we are given a word $w$, is it in the specified language $L$?

Below is the implementation of the recognize algorithm: