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.
Returns:(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.
Returns:(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.
Returns:(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.
Returns:

(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.
Returns:(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.
Returns:(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.
Returns:

(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.
Returns:(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.
Returns:(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.
Returns:

(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’].
Returns:

(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.