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
|
Side effects on input! Removes from the DFA all states that do not reach a final state and returns the pruned DFA. |
|
Returns a DFA that accepts any word but he ones accepted by the input DFA. |
|
Side effects on input! Completes the DFA assigning to each state a transition for each letter in the alphabet (if not already defined). |
|
Returns a DFA accepting the intersection of the DFAs in input. |
|
Returns the minimization of the DFA in input through a greatest fix-point method. |
Checks if the input DFA is nonempty (i.e. |
|
|
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. |
|
Side effects on input! Removes unreachable states from a DFA and returns the pruned DFA. |
|
Side effects on input! Returns the DFA in input trimmed, so both reachable and co-reachable. |
|
Returns a DFA accepting the union of the input DFAs. |
|
Checks if a given word is accepted by a DFA, returning True/false. |
|
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.