# DFA¶

Module to manage DFA (Deterministic Finite Automaton).

Formally a DFA, Deterministic Finite Automaton, is a tuple $$A=(Σ,S,s_0,ρ,F)$$, where:

• Σ is a finite nonempty alphabet;
• S is a finite nonempty set of states;
• $$s_0 ∈ S$$ is the initial state;
• F ⊆ S is the set of accepting states;
• $$ρ: S × Σ → S$$ is a transition function, which can be a partial function.

Intuitively, $$s_0 = ρ(s, a)$$ is the state that A can move into when it is in state s and it reads the symbol a. (If $$ρ(s, a)$$ is undefined then reading a leads to rejection.)

In this module a DFA is defined as follows

DFA = dict() with the following keys-values:
• alphabet => set() ;

• states => set() ;

• initial_state => str() ;

• accepting_states => set() ;

• transitions => dict(), where

key: (state ∈ states, action ∈ alphabet)

value: (arriving_state in states).

List

 dfa_co_reachable(dfa) Side effects on input! Removes from the DFA all states that do not reach a final state and returns the pruned DFA. dfa_complementation(dfa) Returns a DFA that accepts any word but he ones accepted by the input DFA. dfa_completion(dfa) Side effects on input! Completes the DFA assigning to each state a transition for each letter in the alphabet (if not already defined). dfa_intersection(dfa_1, dfa_2) Returns a DFA accepting the intersection of the DFAs in input. dfa_minimization(dfa) Returns the minimization of the DFA in input through a greatest fix-point method. dfa_nonemptiness_check(dfa) Checks if the input DFA is nonempty (i.e. dfa_projection(dfa, symbols_to_remove) Returns a NFA that reads the language recognized by the input DFA where all the symbols in symbols_to_project are projected out of the alphabet. dfa_reachable(dfa) Side effects on input! Removes unreachable states from a DFA and returns the pruned DFA. dfa_trimming(dfa) Side effects on input! Returns the DFA in input trimmed, so both reachable and co-reachable. dfa_union(dfa_1, dfa_2) Returns a DFA accepting the union of the input DFAs. dfa_word_acceptance(dfa, word) Checks if a given word is accepted by a DFA, returning True/false. rename_dfa_states(dfa, suffix) Side effect on input! Renames all the states of the DFA adding a suffix.

Functions

PySimpleAutomata.DFA.dfa_co_reachable(dfa: dict) → dict[source]

Side effects on input! Removes from the DFA all states that do not reach a final state and returns the pruned DFA.

It is possible to remove from a DFA A all states that do not reach a final state without altering the language. The co-reachable dfa $$A_F$$ corresponding to A is defined as:

$$A_F = (Σ, S_F , s_0 , ρ|S_F , F )$$

where

• $$S_F$$ is the set of states that reach a final state
• $$ρ|S_F$$ is the restriction on $$S_F × Σ$$ of ρ.
Parameters: dfa (dict) – input DFA. (dict) representing the pruned DFA.
PySimpleAutomata.DFA.dfa_complementation(dfa: dict) → dict[source]

Returns a DFA that accepts any word but he ones accepted by the input DFA.

Let A be a completed DFA, $$Ā = (Σ, S, s_0 , ρ, S − F )$$ is the DFA that runs A but accepts whatever word A does not.

Parameters: dfa (dict) – input DFA. (dict) representing the complement of the input DFA.
PySimpleAutomata.DFA.dfa_completion(dfa: dict) → dict[source]

Side effects on input! Completes the DFA assigning to each state a transition for each letter in the alphabet (if not already defined).

We say that a DFA is complete if its transition function $$ρ:S×Σ→S$$ is a total function, that is, for all $$s ∈ S$$ and all $$a ∈ Σ$$ we have that exists a $$ρ(s,a)=s_x$$ for some $$s_x ∈ S$$. Given an arbitrary DFA A, its completed version $$A_T$$ is obtained as follows: $$A_T = (Σ, S ∪ \{sink\}, s_0 , ρ_T , F )$$ with $$ρ_T(s,a)=sink$$ when $$ρ(s,a)$$ is not defined in A and $$ρ_T=ρ$$ in the other cases.

Parameters: dfa (dict) – input DFA. (dict) representing the completed DFA.
PySimpleAutomata.DFA.dfa_intersection(dfa_1: dict, dfa_2: dict) → dict[source]

Returns a DFA accepting the intersection of the DFAs in input.

Let $$A_1 = (Σ, S_1 , s_{01} , ρ_1 , F_1 )$$ and $$A_2 = (Σ, S_2 , s_{02} , ρ_2 , F_2 )$$ be two DFAs. Then there is a DFA $$A_∧$$ that runs simultaneously both $$A_1$$ and $$A_2$$ on the input word and accepts when both accept. It is defined as:

$$A_∧ = (Σ, S_1 × S_2 , (s_{01} , s_{02} ), ρ, F_1 × F_2 )$$

where

$$ρ((s_1 , s_2 ), a) = (s_{X1} , s_{X2} )$$ iff $$s_{X1} = ρ_1 (s_1 , a)$$ and $$s_{X2}= ρ_2 (s_2 , a)$$

Implementation proposed guarantees the resulting DFA has only reachable states.

Parameters: dfa_1 (dict) – first input DFA; dfa_2 (dict) – second input DFA. (dict) representing the intersected DFA.
PySimpleAutomata.DFA.dfa_minimization(dfa: dict) → dict[source]

Returns the minimization of the DFA in input through a greatest fix-point method.

Given a completed DFA $$A = (Σ, S, s_0 , ρ, F )$$ there exists a single minimal DFA $$A_m$$ which is equivalent to A, i.e. reads the same language $$L(A) = L(A_m)$$ and with a minimal number of states. To construct such a DFA we exploit bisimulation as a suitable equivalence relation between states.

A bisimulation relation $$E ∈ S × S$$ is a relation between states that satisfies the following condition: if $$(s, t) ∈ E$$ then:

• s ∈ F iff t ∈ F;
• For all $$(s_X,a)$$ such that $$ρ(s, a) = s_X$$, there exists $$t_X$$ such that $$ρ(t, a) = t_X$$ and $$(s_X , t_X ) ∈ E$$;
• For all $$(t_X,a)$$ such that $$ρ(t, a) = t_X$$ , there exists $$s_X$$ such that $$ρ(s, a) = s_X$$ and $$(s_X , t_X ) ∈ E$$.
Parameters: dfa (dict) – input DFA. (dict) representing the minimized DFA.
PySimpleAutomata.DFA.dfa_nonemptiness_check(dfa: dict) → bool[source]

Checks if the input DFA is nonempty (i.e. if it recognizes a language except the empty one), returning True/False.

An automaton A is nonempty if $$L(A) ≠ ∅$$. L(A) is nonempty iff there are states $$s_0 and t ∈ F$$ such that t is connected to $$s_0$$. Thus, automata nonemptiness is equivalent to graph reachability, where a breadth-first-search algorithm can construct in linear time the set of all states connected to initial state $$s_0$$. A is nonempty iff this set intersects F nontrivially.

Parameters: dfa (dict) – input DFA. (bool), True if the DFA is nonempty, False otherwise
PySimpleAutomata.DFA.dfa_projection(dfa: dict, symbols_to_remove: set) → dict[source]

Returns a NFA that reads the language recognized by the input DFA where all the symbols in symbols_to_project are projected out of the alphabet.

Projection in a DFA is the operation that existentially removes from a word all occurrence of symbols in a set X. Given a dfa $$A = (Σ, S, s_0 , ρ, F )$$, we can define an NFA $$A_{πX}$$ that recognizes the language $$πX(L(A))$$ as

$$A_{πX}= ( Σ−X, S, S_0 , ρ_X , F )$$

where

• $$S_0 = \{s | (s_0 , s) ∈ ε_X \}$$
• $$(s,a,s_y ) ∈ ρ_X$$ iff there exist $$(t, t_y)$$ s.t. $$(s,t) ∈ ε_X , t_y = ρ(t,a)$$ and $$(t_y , s_y ) ∈ ε_X$$
Parameters: dfa (dict) – input DFA; symbols_to_remove (set) – set containing symbols ∈ dfa[ ‘alphabet’] to be projected out from DFA. (dict) representing a NFA.
PySimpleAutomata.DFA.dfa_reachable(dfa: dict) → dict[source]

Side effects on input! Removes unreachable states from a DFA and returns the pruned DFA.

It is possible to remove from a DFA A all unreachable states from the initial state without altering the language. The reachable DFA $$A_R$$ corresponding to A is defined as:

$$A_R = (Σ, S_R , s_0 , ρ|S_R , F ∩ S_R )$$

where

• $$S_R$$ set of reachable state from the initial one
• $$ρ|S_R$$ is the restriction on $$S_R × Σ$$ of ρ.
Parameters: dfa (dict) – input DFA. (dict) representing the pruned DFA.
PySimpleAutomata.DFA.dfa_trimming(dfa: dict) → dict[source]

Side effects on input! Returns the DFA in input trimmed, so both reachable and co-reachable.

Given a DFA A, the corresponding trimmed DFA contains only those states that are reachable from the initial state and that lead to a final state. The trimmed dfa $$A_{RF}$$ corresponding to A is defined as

$$A_{RF} = (Σ, S_R ∩ S_F , s_0 , ρ|S_R∩S_F , F ∩ S_R )$$

where

• $$S_R$$ set of reachable states from the initial state
• $$S_F$$ set of states that reaches a final state
• $$ρ|S_R∩S_F$$ is the restriction on $$(S_R ∩ S_F ) × Σ$$ of ρ.
Parameters: dfa (dict) – input DFA. (dict) representing the trimmed input DFA.
PySimpleAutomata.DFA.dfa_union(dfa_1: dict, dfa_2: dict) → dict[source]

Returns a DFA accepting the union of the input DFAs.

Let $$A_1 = (Σ, S_1 , s_{01} , ρ_1 , F_1 )$$ and $$A_2 = (Σ, S_2 , s_{02} , ρ_2 , F_2 )$$ be two completed DFAs. Then there is a DFA $$A_∨$$ that runs simultaneously both $$A_1$$ and $$A_2$$ on the input word and accepts when one of them accepts. It is defined as:

$$A_∨ = (Σ, S_1 × S_2 , (s_{01} , s_{02} ), ρ, (F_1 × S_2 ) ∪ (S_1 × F_2 ))$$

where

$$ρ((s_1 , s_2 ), a) = (s_{X1} , s_{X2} )$$ iff $$s_{X1} = ρ_1 (s_1 , a)$$ and $$s_{X2} = ρ(s_2 , a)$$

Proposed implementation guarantees resulting DFA has only reachable states.

Parameters: dfa_1 (dict) – first input DFA; dfa_2 (dict) – second input DFA. (dict) representing the united DFA.
PySimpleAutomata.DFA.dfa_word_acceptance(dfa: dict, word: list) → bool[source]

Checks if a given word is accepted by a DFA, returning True/false.

The word w is accepted by a DFA if DFA has an accepting run on w. Since A is deterministic, $$w ∈ L(A)$$ if and only if $$ρ(s_0 , w) ∈ F$$ .

Parameters: dfa (dict) – input DFA; word (list) – list of actions ∈ dfa[‘alphabet’]. (bool), True if the word is accepted, False in the other case.
PySimpleAutomata.DFA.rename_dfa_states(dfa: dict, suffix: str)[source]

Side effect on input! Renames all the states of the DFA adding a suffix.

It is an utility function to be used to avoid automata to have states with names in common.

Avoid suffix that can lead to special name like “as”, “and”,…

Parameters: dfa (dict) – input DFA. suffix (str) – string to be added at beginning of each state name.