NFA

Module to manage NFA (Nondeterministic Finite Automata).

Formally a NFA, Nondeterministic Finite Automaton, is a tuple \((Σ, S, S^0 , ρ, F )\), where

• Σ is a finite nonempty alphabet;

• S is a finite nonempty set of states;

• \(S^0\) is the nonempty set of initial states;

• F is the set of accepting states;

• \(ρ: S × Σ × S\) is a transition relation. Intuitively, \((s, a, s' ) ∈ ρ\) states that A can move from s into s’ when it reads the symbol a. It is allowed that \((s, a, s' ) ∈ ρ\) and \((s, a, s'' ) ∈ ρ\) with \(S' ≠ S''\) .

In this module a NFA is defined as follows

NFA = dict() with the following keys-values:

• alphabet => set() ;

• states => set() ;

• initial_states => set() ;

• accepting_states => set() ;

• transitions => dict(), where

  key: (state in states, action in alphabet)

  value: {set of arriving states in states}.

List

nfa_complementation(nfa)	Returns a DFA reading the complemented language read by input NFA.
nfa_determinization(nfa)	Returns a DFA that reads the same language of the input NFA.
nfa_interestingness_check(nfa)	Checks if the input NFA is interesting, returning True/False.
nfa_intersection(nfa_1, nfa_2)	Returns a NFA that reads the intersection of the NFAs in input.
nfa_nonemptiness_check(nfa)	Checks if the input NFA reads any language other than the empty one, returning True/False.
nfa_nonuniversality_check(nfa)	Checks if the language read by the input NFA is different from Σ∗ (i.e.
nfa_union(nfa_1, nfa_2)	Returns a NFA that reads the union of the NFAs in input.
nfa_word_acceptance(nfa, word)	Checks if a given word is accepted by a NFA.
rename_nfa_states(nfa, suffix)	Side effect on input! Renames all the states of the NFA adding a suffix.

Functions

PySimpleAutomata.NFA.nfa_complementation(nfa: dict) → dict

Returns a DFA reading the complemented language read by input NFA.

Complement a nondeterministic automaton is possible complementing the determinization of it. The construction is effective, but it involves an exponential blow-up, since determinization involves an unavoidable exponential blow-up (i.e., if NFA has n states, then the DFA has \(2^n\) states).

Parameters:

nfa (dict) – input NFA.

Returns:

(dict) representing a completed DFA.

PySimpleAutomata.NFA.nfa_determinization(nfa: dict) → dict

Returns a DFA that reads the same language of the input NFA.

Let A be an NFA, then there exists a DFA \(A_d\) such that \(L(A_d) = L(A)\). Intuitively, \(A_d\) collapses all possible runs of A on a given input word into one run over a larger state set. \(A_d\) is defined as:

\(A_d = (Σ, 2^S , s_0 , ρ_d , F_d )\)

where:

• \(2^S\) , i.e., the state set of \(A_d\) , consists of all sets of states S in A;

• \(s_0 = S^0\) , i.e., the single initial state of \(A_d\) is the set \(S_0\) of initial states of A;

• \(F_d = \{Q | Q ∩ F ≠ ∅\}\), i.e., the collection of sets of states that intersect F nontrivially;

• \(ρ_d(Q, a) = \{s' | (s,a, s' ) ∈ ρ\ for\ some\ s ∈ Q\}\).

Parameters:

nfa (dict) – input NFA.

Returns:

(dict) representing a DFA

PySimpleAutomata.NFA.nfa_interestingness_check(nfa: dict) → bool

Checks if the input NFA is interesting, returning True/False.

An automaton is “interesting” if it defines an “interesting” language, i.e., a language that is neither empty nor contains all possible words.

Parameters:

nfa (dict) – input NFA.

Returns:

(bool), True if the input nfa is interesting, False otherwise.

PySimpleAutomata.NFA.nfa_intersection(nfa_1: dict, nfa_2: dict) → dict

Returns a NFA that reads the intersection of the NFAs in input.

Let \(A_1 = (Σ,S_1,S_1^0,ρ_1,F_1)\) and \(A_2 =(Σ, S_2,S_2^0,ρ_2,F_2)\) be two NFAs. There is a NFA \(A_∧\) that runs simultaneously both \(A_1\) and \(A_2\) on the input word, so \(L(A_∧) = L(A_1)∩L(A_2)\). It is defined as:

\(A_∧ = ( Σ , S , S_0 , ρ , F )\)

where

• \(S = S_1 × S_2\)

• \(S_0 = S_1^0 × S_2^0\)

• \(F = F_1 × F_2\)

• \(((s,t), a, (s_X , t_X)) ∈ ρ\) iff \((s, a,s_X ) ∈ ρ_1\) and \((t, a, t_X ) ∈ ρ_2\)

Parameters:

• nfa_1 (dict) – first input NFA;

• nfa_2 (dict) – second input NFA;

Returns:

(dict) representing the intersected NFA.

PySimpleAutomata.NFA.nfa_nonemptiness_check(nfa: dict) → bool

Checks if the input NFA reads any language other than the empty one, returning True/False.

The language L(A) recognized by the automaton A is nonempty iff there are states \(s ∈ S_0\) and \(t ∈ F\) such that t is connected to s. Thus, automata nonemptiness is equivalent to graph reachability.

A breadth-first-search algorithm can construct in linear time the set of all states connected to a state in \(S_0\). A is nonempty iff this set intersects F nontrivially.

Parameters:

nfa (dict) – input NFA.

Returns:

(bool), True if the input nfa is nonempty, False otherwise.

PySimpleAutomata.NFA.nfa_nonuniversality_check(nfa: dict) → bool

Checks if the language read by the input NFA is different from Σ∗ (i.e. contains all possible words), returning True/False.

To test nfa A for nonuniversality, it suffices to test Ā ( complementary automaton of A) for nonemptiness

Parameters:

nfa (dict) – input NFA.

Returns:

(bool), True if input nfa is nonuniversal, False otherwise.

PySimpleAutomata.NFA.nfa_union(nfa_1: dict, nfa_2: dict) → dict

Returns a NFA that reads the union of the NFAs in input.

Let \(A_1 = (Σ,S_1,S_1^0,ρ_1,F_1)\) and \(A_2 =(Σ, S_2,S_2^0,ρ_2,F_2)\) be two NFAs. here is a NFA \(A_∨\) that nondeterministically chooses \(A_1\) or \(A_2\) and runs it on the input word. It is defined as:

\(A_∨ = (Σ, S, S_0 , ρ, F )\)

where:

• \(S = S_1 ∪ S_2\)

• \(S_0 = S_1^0 ∪ S_2^0\)

• \(F = F_1 ∪ F_2\)

• \(ρ = ρ_1 ∪ ρ_2\) , that is \((s, a, s' ) ∈ ρ\) if \([ s ∈ S_1\ and\ (s, a, s' ) ∈ ρ_1 ]\) OR \([ s ∈ S_2\ and\ (s, a, s' ) ∈ ρ_2 ]\)

Pay attention to avoid having the NFAs with state names in common, in case use PySimpleAutomata.NFA.rename_nfa_states function.

Parameters:

• nfa_1 (dict) – first input NFA;

• nfa_2 (dict) – second input NFA.

Returns:

(dict) representing the united NFA.

PySimpleAutomata.NFA.nfa_word_acceptance(nfa: dict, word: list) → bool

Checks if a given word is accepted by a NFA.

The word w is accepted by a NFA if exists at least an accepting run on w.

Parameters:

• nfa (dict) – input NFA;

• word (list) – list of symbols ∈ nfa[‘alphabet’];

Returns:

(bool), True if the word is accepted, False otherwise.

PySimpleAutomata.NFA.rename_nfa_states(nfa: dict, suffix: str)

Side effect on input! Renames all the states of the NFA 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:

• nfa (dict) – input NFA.

• suffix (str) – string to be added at beginning of each state name.