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[source]

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[source]

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[source]

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[source]

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[source]

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[source]

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[source]

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[source]

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)[source]

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.