---
title: "Deterministic Finite Automata"
type: concept
related: [Pac Learning, Regular Expression Complexity, Myhill Nerode, Deterministic Finite Automata, Minimizing Dfas]
source: https://www.jemoka.com/posts/kbhdeterministic_finite_automata/
confidence: high
status: active
---

Computational memory of this type of model is fixed. In particular, the class of problems this type of automata solves (&ldquo;languages it recognizes&rdquo;) 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, &hellip;, w_{n} \in \Sigma\), and \(w = w_1 &hellip; w_{n} \in \Sigma^{*}\), \(M\) accepts \(w\) if there exists \(r_0, &hellip;, r_{n} \in Q\) such that:
\(r_{0} = q_{0}\) \(\delta(r_{i}, w_{i+1}) = r_{i+1}\) for all \(i=0, &hellip;, n-{1}\), and \(r_{n} \in F\) additional information L(M) the set of all strings that \(M\) accepts is called the &ldquo;language recognized by \(M\)&rdquo;, or &ldquo;the function computed by \(M\)&rdquo;.
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\)
regular language see regular language
DFAs are equivalent to NFAs see DFAs are equivalent to NFAs
DFAs recognize the same set of languages as NFAs, that is, regular languages.
regular expressions see regular expression
examples and factoids why DFAs? constant size memory =&gt; important, dynamically adding memory does bring more computational power read input once =&gt; unimportant, being able to go back and fourth doesn&rsquo;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&rsquo;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 &hellip;. 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 pumping lemma see pumping lemma
Minimizing DFAs see Minimizing DFAs
Learning DFA See PAC Learning
