# 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]

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