Deterministic Finite Automata

Computational memory of this type of model is fixed. In particular, the class of problems this type of automata solves (“languages it recognizes”) is called regular languages.

We want to explore the closure properties of regular languages (does combining regular languages result in regular languages)

constituents

A DFA is a five-tuple \(M = (Q, \Sigma, \delta, q_{0}, F)\).

\(Q\): finite set of all states
\(\Sigma\): the alphabet
\(\delta: Q \times \Sigma \to Q\), the transition function
\(q_0 \in Q\): the start state
\(F \subseteq Q\): the accept states, which means we accept the input string we got if after processing the string we ended up at one of these states

requirements

if processing an input results in an accepting state, we accept the input; otherwise, we reject the input. this is the computation.

accept

Let \(w_1, …, w_{n} \in \Sigma\), and \(w = w_1 … w_{n} \in \Sigma^{*}\), \(M\) accepts \(w\) if there exists \(r_0, …, r_{n} \in Q\) such that:

\(r_{0} = q_{0}\)
\(\delta(r_{i}, w_{i+1}) = r_{i+1}\) for all \(i=0, …, n-{1}\), and
\(r_{n} \in F\)

additional information

L(M)

the set of all strings that \(M\) accepts is called the “language recognized by \(M\)”, or “the function computed by \(M\)”.

important factoid: empty language is not the empty string, the empty language contains no strings, the empty string contains no content, which means you stay at \(q_0\)

examples and factoids

why DFAs?

constant size memory => important, dynamically adding memory does bring more computational power
read input once => unimportant, being able to go back and fourth doesn’t add additional computational power

original introduction of nondeterminism

Limitations of DFAs

pumping lemma
Myhill-Nerode (entire characterization of regular languages)

simple things to make and do with DFAs because they are so simple

optimize DFA: for a given regular language, what is the smallest DFA?
learning DFA

examples

proof: this language accepts an odd number of \(1\)

We show this by induction on the string length.

base, this string has zero length, and we reject the string
suppose for a string of length \(n\), \(M\) accepts \(n\) IFF \(n\) has an odd number of \(1\)
now, consider a string of length \(n+1\), casework:
- we are at an accept state, and we got a \(0\): this means we still have an odd number of \(1\), we don’t go anywhere, we can accept
- we are at an reject state, and we got a \(1\): this means we now have an odd number of \(1\), we go to \(q\), and we can accept
- ….

build a DFA that accepts at least strings that contain \(001\)

this requires some thinking, and the trick is simply keeping track of what you saw in the states, and if you saw something contradictory backtrak if needed

constructing a binary addition system