Deterministic Finite Automata (DFAs)

A deterministic finite automaton (DFA) is a mathematical model used to recognize patterns in strings. It is a type of finite state machine that accepts or rejects a given string based on its current state and the input it receives.

Formal definition

A DFA is defined as a 5-tuple, consisting of:

A finite set of states Q
A finite set of input symbols Σ (also called the alphabet)
A transition function δ : Q × Σ → Q, which maps a state and an input symbol to a new state
A start state q₀ ∈ Q
A set of accept states F ⊆ Q

How DFAs work

A DFA starts in the start state and reads a string of input symbols. For each symbol, it transitions to a new state based on the current state and the symbol. If the final state is an accept state, the string is accepted; otherwise, it is rejected.

Example

Let’s consider a DFA that recognizes strings of 0’s and 1’s that have an odd number of 1’s. The DFA has two states: q₀ and q₁. The transition function is defined as follows:

δ(q₀, 0) = q₀ δ(q₀, 1) = q₁ δ(q₁, 0) = q₁ δ(q₁, 1) = q₀ The start state is q₀ and the accept state is q₁.

Let’s see how the DFA processes the string “11010”:

q0 –(1)–> q1 –(1)–> q0 –(0)–> q0 –(1)–> q1 –(0)–> q1 The final state is q₁, which is an accept state. Therefore, the string “11010” is accepted by the DFA.

slides

Conclusion:

DFAs are a powerful tool for recognizing patterns in strings. They can be used in a wide range of applications, such as lexical analysis, regular expression matching, and compiler design. Understanding DFAs is an important part of computer science and is essential for building robust software systems.

Repository

Algorithms DFA

This is some sample java maven project with a package for FDA proofs

repository

References

* https://ivanvladimir.gitlab.io/lfya_book/docs/02lam%C3%A1quinasinmemoria/04aut%C3%B3matafinito/ * https://colab.research.google.com/github/ivanvladimir/maquinas_notebooks/blob/main/lfya/02%20La%20m%C3%A1quina%20sin%20memoria.ipynb