Finite Automaton

pyformlang.finite_automaton

This module deals with finite state automata.

Available Classes

FiniteAutomaton

A general representation of automata. Cannot be used directly.

DeterministicFiniteAutomaton

A deterministic finite automaton

NondeterministicFiniteAutomaton

A non-deterministic finite automaton, without epsilon transitions

EpsilonNFA

A non-deterministic finite automaton, with epsilon transitions

TransitionFunction

A deterministic transition function

NondeterministicTransitionFunction

A non-deterministic transition function

State

A state (or node) in an automaton

Symbol

A symbol (part of the alphabet) in an automaton

Epsilon

The epsilon (or empty) symbol

DuplicateTransitionError

An error that occurs when trying to add a non-deterministic edge to a deterministic automaton

InvalidEpsilonTransition

An exception that occurs when adding an epsilon transition to a non-epsilon NFA.

class pyformlang.finite_automaton.DeterministicFiniteAutomaton(states: Optional[AbstractSet[pyformlang.finite_automaton.state.State]] = None, input_symbols: Optional[AbstractSet[pyformlang.finite_automaton.symbol.Symbol]] = None, transition_function: Optional[pyformlang.finite_automaton.transition_function.TransitionFunction] = None, start_state: Optional[pyformlang.finite_automaton.state.State] = None, final_states: Optional[AbstractSet[pyformlang.finite_automaton.state.State]] = None)[source]

Represents a deterministic finite automaton

This class represents a deterministic finite automaton.

Parameters
  • states (set of State, optional) – A finite set of states

  • input_symbols (set of Symbol, optional) – A finite set of input symbols

  • transition_function (TransitionFunction, optional) – Takes as arguments a state and an input symbol and returns a state.

  • start_state (State, optional) – A start state, element of states

  • final_states (set of State, optional) – A set of final or accepting states. It is a subset of states.

Examples

>>> dfa = DeterministicFiniteAutomaton()

Creates an empty deterministic finite automaton.

>>> dfa.add_transitions([(0, "abc", 1), (0, "d", 1)])

Adds two transitions to the deterministic finite automaton. One goes from the state 0 to the state 1 when reading the string “abc”. The other also goes from the state 0 to the state 1 when reading the string “d”.

>>> dfa.add_start_state(0)

Adds the start state, 0 here.

>>> dfa.add_final_state(1)

Adds a final state, 1 here.

>>> dfa.is_deterministic()
True

Checks if the automaton is deterministic. True here.

>>> dfa.accepts(["abc"])
True

Checks if the automaton recognize the word composed of a single letter, “abc”.

accepts(word: Iterable[pyformlang.finite_automaton.symbol.Symbol]) bool[source]

Checks whether the dfa accepts a given word

Parameters

word (iterable of Symbol) – A sequence of input symbols

Returns

is_accepted – Whether the word is accepted or not

Return type

bool

Examples

>>> dfa = DeterministicFiniteAutomaton()
>>> dfa.add_transitions([(0, "abc", 1), (0, "d", 1)])
>>> dfa.add_start_state(0)
>>> dfa.add_final_state(1)
>>> dfa.accepts(["abc"])
True
add_start_state(state: pyformlang.finite_automaton.state.State) int[source]

Set an initial state

Parameters

state (State) – The new initial state

Returns

done – 1 is correctly added

Return type

int

Examples

>>> dfa = DeterministicFiniteAutomaton()
>>> dfa.add_start_state(0)
copy() pyformlang.finite_automaton.deterministic_finite_automaton.DeterministicFiniteAutomaton[source]

Copies the current DFA

Returns

enfa – A copy of the current DFA

Return type

DeterministicFiniteAutomaton

Examples

>>> dfa = DeterministicFiniteAutomaton()
>>> dfa.add_transitions([(0, "abc", 1), (0, "d", 1)])
>>> dfa.add_start_state(0)
>>> dfa.add_final_state(1)
>>> dfa_copy = dfa.copy()
>>> dfa.is_equivalent_to(dfa_copy)
True
is_deterministic() bool[source]

Checks whether an automaton is deterministic

Returns

is_deterministic – Whether the automaton is deterministic

Return type

bool

Examples

>>> dfa = DeterministicFiniteAutomaton()
>>> dfa.is_deterministic()
True
is_equivalent_to(other)[source]

Check whether two automata are equivalent

Parameters

other (FiniteAutomaton) – A sequence of input symbols

Returns

are_equivalent – Whether the two automata are equivalent or not

Return type

bool

Examples

>>> dfa = DeterministicFiniteAutomaton()
>>> dfa.add_transitions([(0, "abc", 1), (0, "d", 1)])
>>> dfa.add_start_state(0)
>>> dfa.add_final_state(1)
>>> dfa_minimal = dfa.minimize()
>>> dfa.is_equivalent_to(dfa_minimal)
True
minimize() pyformlang.finite_automaton.deterministic_finite_automaton.DeterministicFiniteAutomaton[source]

Minimize the current DFA

Returns

dfa – The minimal DFA

Return type

DeterministicFiniteAutomaton

Examples

>>> dfa = DeterministicFiniteAutomaton()
>>> dfa.add_transitions([(0, "abc", 1), (0, "d", 1)])
>>> dfa.add_start_state(0)
>>> dfa.add_final_state(1)
>>> dfa_minimal = dfa.minimize()
>>> dfa.is_equivalent_to(dfa_minimal)
True
remove_start_state(state: pyformlang.finite_automaton.state.State) int[source]

remove an initial state

Parameters

state (State) – The new initial state

Returns

done – 1 is correctly added

Return type

int

Examples

>>> dfa = DeterministicFiniteAutomaton()
>>> dfa.add_start_state(0)
>>> dfa.remove_start_state(0)
property start_state: pyformlang.finite_automaton.state.State

The start state

to_deterministic() pyformlang.finite_automaton.deterministic_finite_automaton.DeterministicFiniteAutomaton[source]

Transforms the current automaton into a dfa. Does nothing if the automaton is already deterministic.

Returns

dfa – A dfa equivalent to the current nfa

Return type

DeterministicFiniteAutomaton

Examples

>>> dfa0 = DeterministicFiniteAutomaton()
>>> dfa1 = dfa.to_deterministic()
>>> dfa0.is_equivalent_to(dfa1)
True
exception pyformlang.finite_automaton.DuplicateTransitionError(s_from: pyformlang.finite_automaton.state.State, symb_by: pyformlang.finite_automaton.symbol.Symbol, s_to: pyformlang.finite_automaton.state.State, s_to_old: pyformlang.finite_automaton.state.State)[source]

Signals a duplicated transition

Parameters
  • s_from (State) – The source state

  • symb_by (Symbol) – The transition symbol

  • s_to (State) – The wanted new destination state

  • s_to_old (State) – The old destination state

message

An error message summarising the information

Type

str

class pyformlang.finite_automaton.Epsilon[source]

An epsilon transition

Examples

>>> epsilon = Epsilon()
class pyformlang.finite_automaton.EpsilonNFA(states: Optional[AbstractSet[pyformlang.finite_automaton.state.State]] = None, input_symbols: Optional[AbstractSet[pyformlang.finite_automaton.symbol.Symbol]] = None, transition_function: Optional[pyformlang.finite_automaton.nondeterministic_transition_function.NondeterministicTransitionFunction] = None, start_state: Optional[AbstractSet[pyformlang.finite_automaton.state.State]] = None, final_states: Optional[AbstractSet[pyformlang.finite_automaton.state.State]] = None)[source]

Represents an epsilon NFA

Parameters
  • states (set of State, optional) – A finite set of states

  • input_symbols (set of Symbol, optional) – A finite set of input symbols

  • transition_function (NondeterministicTransitionFunction, optional) – Takes as arguments a state and an input symbol and returns a state.

  • start_state (set of State, optional) – A start state, element of states

  • final_states (set of State, optional) – A set of final or accepting states. It is a subset of states.

Examples

>>> enfa = EpsilonNFA()

Creates an empty epsilon non-deterministic automaton.

>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1), (0, "epsilon", 2)])

Adds three transition, one of them being an epsilon transition.

>>> enfa.add_start_state(0)

Adds a start state.

>>> enfa.add_final_state(1)

Adds a final state.

>>> enfa.is_deterministic()
False

Checks if the automaton is deterministic.

accepts(word: Iterable[pyformlang.finite_automaton.symbol.Symbol]) bool[source]

Checks whether the epsilon nfa accepts a given word

Parameters

word (iterable of Symbol) – A sequence of input symbols

Returns

is_accepted – Whether the word is accepted or not

Return type

bool

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> enfa.accepts(["abc", "epsilon"])
True
>>> enfa.accepts(["epsilon"])
False
copy() pyformlang.finite_automaton.epsilon_nfa.EpsilonNFA[source]

Copies the current Epsilon NFA

Returns

enfa – A copy of the current Epsilon NFA

Return type

EpsilonNFA

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> enfa_copy = enfa.copy()
>>> enfa.is_equivalent_to(enfa_copy)
True
eclose(state: pyformlang.finite_automaton.state.State) Set[pyformlang.finite_automaton.state.State][source]

Compute the epsilon closure of a state

Parameters

state (State) – The source state

Returns

states – The epsilon closure of the source state

Return type

set of State

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> enfa.eclose(0)
{2}
eclose_iterable(states: Iterable[pyformlang.finite_automaton.state.State]) Set[pyformlang.finite_automaton.state.State][source]

Compute the epsilon closure of a collection of states

Parameters

states (iterable of State) – The source states

Returns

states – The epsilon closure of the source state

Return type

set of State

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> enfa.eclose_iterable([0])
{2}
get_complement() pyformlang.finite_automaton.epsilon_nfa.EpsilonNFA[source]

Get the complement of the current Epsilon NFA

Equivalent to:

>>> -automaton
Returns

enfa – A complement automaton

Return type

EpsilonNFA

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> enfa_complement = enfa.get_complement()
>>> enfa_complement.accepts(["epsilon"])
True
>>> enfa_complement.accepts(["abc"])
False
get_difference(other: pyformlang.finite_automaton.epsilon_nfa.EpsilonNFA) pyformlang.finite_automaton.epsilon_nfa.EpsilonNFA[source]

Compute the difference with another Epsilon NFA

Equivalent to:

>>> automaton0 - automaton1
Parameters

other (EpsilonNFA) – The other Epsilon NFA

Returns

enfa – The difference with the other epsilon NFA

Return type

EpsilonNFA

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> enfa2 = EpsilonNFA()
>>> enfa2.add_transition(0, "d", 1)
>>> enfa2.add_final_state(1)
>>> enfa2.add_start_state(0)
>>> enfa_diff = enfa.get_difference(enfa2)
>>> enfa_diff.accepts(["d"])
False
>>> enfa_diff.accepts(["abc"])
True
get_intersection(other: pyformlang.finite_automaton.epsilon_nfa.EpsilonNFA) pyformlang.finite_automaton.epsilon_nfa.EpsilonNFA[source]

Computes the intersection of two Epsilon NFAs

Equivalent to:

>>> automaton0 and automaton1
Parameters

other (EpsilonNFA) – The other Epsilon NFA

Returns

enfa – The intersection of the two Epsilon NFAs

Return type

EpsilonNFA

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> enfa2 = EpsilonNFA()
>>> enfa2.add_transition(0, "d", 1)
>>> enfa2.add_final_state(1)
>>> enfa2.add_start_state(0)
>>> enfa_inter = enfa.get_intersection(enfa2)
>>> enfa_inter.accepts(["abc"])
False
>>> enfa_inter.accepts(["d"])
True
is_deterministic() bool[source]

Checks whether an automaton is deterministic

Returns

is_deterministic – Whether the automaton is deterministic

Return type

bool

Examples

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> enfa.is_deterministic()
False
is_empty() bool[source]

Checks if the language represented by the FSM is empty or not

Returns

is_empty – Whether the language is empty or not

Return type

bool

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> enfa.is_empty()
False
minimize() DeterministicFiniteAutomaton[source]

Minimize the current epsilon NFA

Returns

dfa – The minimal DFA

Return type

DeterministicFiniteAutomaton

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> dfa_minimal = enfa.minimize()
>>> dfa_minimal.is_equivalent(enfa)
True
reverse() pyformlang.finite_automaton.epsilon_nfa.EpsilonNFA[source]

Compute the reversed EpsilonNFA

Equivalent to:

>> ~automaton

Returns

enfa – The reversed automaton

Return type

EpsilonNFA

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (1, "d", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(2)
>>> enfa_reverse = enfa.reverse()
>>> enfa_reverse.accepts(["d", "abc"])
True
to_deterministic() DeterministicFiniteAutomaton[source]

Transforms the epsilon-nfa into a dfa

Returns

dfa – A dfa equivalent to the current nfa

Return type

DeterministicFiniteAutomaton

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> dfa = enfa.to_deterministic()
>>> dfa.is_deterministic()
True
>>> enfa.is_equivalent_to(dfa)
True
to_regex() Regex[source]

Transforms the EpsilonNFA to a regular expression

Returns

regex – A regular expression equivalent to the current Epsilon NFA

Return type

Regex

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> regex = enfa.to_regex()
>>> regex.accepts(["abc"])
True
class pyformlang.finite_automaton.FiniteAutomaton[source]

Represents a general finite automaton

_states

A finite set of states

Type

set of State, optional

_input_symbols

A finite set of input symbols

Type

set of Symbol, optional

_transition_function

Takes as arguments a state and an input symbol and returns a state.

Type

NondeterministicTransitionFunction , optional

_start_state

A start state, element of states

Type

set of State, optional

_final_states

A set of final or accepting states. It is a subset of states.

Type

set of State, optional

add_final_state(state: pyformlang.finite_automaton.state.State) int[source]

Adds a new final state

Parameters

state (State) – A new final state

Returns

done – 1 is correctly added

Return type

int

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
add_start_state(state: pyformlang.finite_automaton.state.State) int[source]

Set an initial state

Parameters

state (State) – The new initial state

Returns

done – 1 is correctly added

Return type

int

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
add_symbol(symbol: pyformlang.finite_automaton.symbol.Symbol)[source]

Add a symbol

Parameters

symbol (Symbol) – The symbol

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_symbol("a")
add_transition(s_from: pyformlang.finite_automaton.state.State, symb_by: pyformlang.finite_automaton.symbol.Symbol, s_to: pyformlang.finite_automaton.state.State) int[source]

Adds a transition to the nfa

Parameters
  • s_from (State) – The source state

  • symb_by (Symbol) – The transition symbol

  • s_to (State) – The destination state

Returns

done – Always 1

Return type

int

Raises

DuplicateTransitionError – If the transition already exists

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transition(0, "abc", 1)
add_transitions(transitions_list)[source]

Adds several transitions to the automaton

Parameters

transitions_list (list of triples of (s_from, symb_by, s_to)) – A list of all the transitions represented as triples as they would be used in add_transition

Returns

done – Always 1

Return type

int

Raises

DuplicateTransitionError – If the transition already exists

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
property final_states

The final states

classmethod from_networkx(graph)[source]

Import a networkx graph into an finite state automaton. The imported graph requires to have the good format, i.e. to come from the function to_networkx

Parameters

graph – The graph representation of the automaton

Returns

A epsilon nondeterministic finite automaton read from the graph

Return type

enfa

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> graph = enfa.to_networkx()
>>> enfa_from_nx = EpsilonNFA.from_networkx(graph)
get_number_transitions() int[source]

Gives the number of transitions

Returns

n_transitions – The number of deterministic transitions

Return type

int

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.get_number_transitions()
3
is_acyclic() bool[source]

Checks if the automaton is acyclic

Returns

is_acyclic – Whether the automaton is acyclic or not

Return type

bool

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> enfa.is_acyclic()
True
is_deterministic()[source]

Checks if the automaton is deterministic

is_equivalent_to(other)[source]

Checks if the current automaton is equivalent to a given one.

Parameters

other – An other finite state automaton

Returns

is_equivalent – Whether the two automata are equivalent or not

Return type

bool

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> dfa = enfa.to_deterministic()
>>> dfa.is_deterministic()
True
is_final_state(state: pyformlang.finite_automaton.state.State) bool[source]

Checks if a state is final

Parameters

state (State) – The state to check

Returns

is_final – Whether the state is final or not

Return type

bool

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> enfa.is_final_state(1)
True
remove_final_state(state: pyformlang.finite_automaton.state.State) int[source]

Remove a final state

Parameters

state (State) – A final state to remove

Returns

done – 0 if it was not a final state, 1 otherwise

Return type

int

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> enfa.remove_final_state(1)
remove_start_state(state: pyformlang.finite_automaton.state.State) int[source]

remove an initial state

Parameters

state (State) – The new initial state

Returns

done – 1 is correctly added

Return type

int

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.remove_start_state(0)
remove_transition(s_from: pyformlang.finite_automaton.state.State, symb_by: pyformlang.finite_automaton.symbol.Symbol, s_to: pyformlang.finite_automaton.state.State) int[source]

Remove a transition of the nfa

Parameters
  • s_from (State) – The source state

  • symb_by (Symbol) – The transition symbol

  • s_to (State) – The destination state

Returns

done – 1 if the transition existed, 0 otherwise

Return type

int

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transition(0, "abc", 1)
>>> enfa.remove_transition(0, "abc", 1)
property start_states

The start states

property states

Gives the states

Returns

states – The states

Return type

set of State

property symbols

The symbols

to_deterministic()[source]

Turns the automaton into a deterministic one

to_dict()[source]

Get the dictionary representation of the transition function. The keys of the dictionary are the source nodes. The items are dictionaries where the keys are the symbols of the transitions and the items are the set of target nodes.

Returns

transition_dict – The transitions as a dictionary.

Return type

dict

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> enfa_dict = enfa.to_dict()
to_fst() pyformlang.fst.fst.FST[source]

Turns the finite automaton into a finite state transducer

The transducers accepts only the words in the language of the automaton and output the input word

Returns

fst – The equivalent FST

Return type

FST

Examples

>>> enfa = EpsilonNFA()
>>> fst = enfa.to_fst()
>>> fst.states
{}
to_networkx() networkx.classes.multidigraph.MultiDiGraph[source]

Transform the current automaton into a networkx graph

Returns

graph – A networkx MultiDiGraph representing the automaton

Return type

networkx.MultiDiGraph

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> graph = enfa.to_networkx()
write_as_dot(filename)[source]

Write the automaton in dot format into a file

Parameters

filename (str) – The filename where to write the dot file

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transitions([(0, "abc", 1), (0, "d", 1),         (0, "epsilon", 2)])
>>> enfa.add_start_state(0)
>>> enfa.add_final_state(1)
>>> enfa.write_as_dot("enfa.dot")
exception pyformlang.finite_automaton.InvalidEpsilonTransition[source]

Exception raised when an epsilon transition is created in deterministic automaton

class pyformlang.finite_automaton.NondeterministicFiniteAutomaton(states: Optional[AbstractSet[pyformlang.finite_automaton.state.State]] = None, input_symbols: Optional[AbstractSet[pyformlang.finite_automaton.symbol.Symbol]] = None, transition_function: Optional[pyformlang.finite_automaton.nondeterministic_transition_function.NondeterministicTransitionFunction] = None, start_state: Optional[AbstractSet[pyformlang.finite_automaton.state.State]] = None, final_states: Optional[AbstractSet[pyformlang.finite_automaton.state.State]] = None)[source]

Represents a nondeterministic finite automaton

This class represents a nondeterministic finite automaton, where epsilon transition are forbidden.

Parameters
  • states (set of State, optional) – A finite set of states

  • input_symbols (set of Symbol, optional) – A finite set of input symbols

  • transition_function (NondeterministicTransitionFunction , optional) – Takes as arguments a state and an input symbol and returns a state.

  • start_state (State, optional) – A start state, element of states

  • final_states (set of State, optional) – A set of final or accepting states. It is a subset of states.

Examples

>>> nfa = NondeterministicFiniteAutomaton()

Creates the NFA.

>>> nfa.add_transitions([(0, "a", 1), (0, "a", 2)])

Adds two transitions.

>>> nfa.add_start_state(0)

Adds a start state.

>>> nfa.add_final_state(1)

Adds a final state.

>>> nfa.accepts(["a"])
True
>>> nfa.is_deterministic()
False
accepts(word: Iterable[pyformlang.finite_automaton.symbol.Symbol]) bool[source]

Checks whether the nfa accepts a given word

Parameters

word (iterable of Symbol) – A sequence of input symbols

Returns

is_accepted – Whether the word is accepted or not

Return type

bool

Examples

>>> nfa = NondeterministicFiniteAutomaton()
>>> nfa.add_transitions([(0, "a", 1), (0, "a", 2)])
>>> nfa.add_start_state(0)
>>> nfa.add_final_state(1)
>>> nfa.accepts(["a"])
True
add_transition(s_from: pyformlang.finite_automaton.state.State, symb_by: pyformlang.finite_automaton.symbol.Symbol, s_to: pyformlang.finite_automaton.state.State) int[source]

Adds a transition to the nfa

Parameters
  • s_from (State) – The source state

  • symb_by (Symbol) – The transition symbol

  • s_to (State) – The destination state

Returns

done – Always 1

Return type

int

Raises

DuplicateTransitionError – If the transition already exists

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_transition(0, "abc", 1)
is_deterministic() bool[source]

Checks whether an automaton is deterministic

Returns

is_deterministic – Whether the automaton is deterministic

Return type

bool

Examples

>>> nfa = NondeterministicFiniteAutomaton()
>>> nfa.add_transitions([(0, "a", 1), (0, "a", 2)])
>>> nfa.add_start_state(0)
>>> nfa.add_final_state(1)
>>> nfa.is_deterministic()
False
to_deterministic() DeterministicFiniteAutomaton[source]

Transforms the nfa into a dfa

Returns

dfa – A dfa equivalent to the current nfa

Return type

DeterministicFiniteAutomaton

Examples

>>> nfa = NondeterministicFiniteAutomaton()
>>> nfa.add_transitions([(0, "a", 1), (0, "a", 2)])
>>> nfa.add_start_state(0)
>>> nfa.add_final_state(1)
>>> dfa = nfa.to_deterministic()
>>> nfa.is_equivalent_to(dfa)
True
class pyformlang.finite_automaton.NondeterministicTransitionFunction[source]

A nondeterministic transition function in a finite automaton.

The difference with a deterministic transition is that the return value is a set of States

Examples

>>> transition = NondeterministicTransitionFunction()
>>> transition.add_transition(State(0), Symbol("a"), State(1))

Creates a transition function and adds a transition.

add_transition(s_from: pyformlang.finite_automaton.state.State, symb_by: pyformlang.finite_automaton.symbol.Symbol, s_to: pyformlang.finite_automaton.state.State) int[source]

Adds a new transition to the function

Parameters
  • s_from (State) – The source state

  • symb_by (Symbol) – The transition symbol

  • s_to (State) – The destination state

Returns

done – Always 1

Return type

int

Examples

>>> transition = NondeterministicTransitionFunction()
>>> transition.add_transition(State(0), Symbol("a"), State(1))
get_edges()[source]

Gets the edges

Returns

edges – A generator of edges

Return type

generator of (State, Symbol, State)

get_number_transitions() int[source]

Gives the number of transitions describe by the function

Returns

n_transitions – The number of transitions

Return type

int

Examples

>>> transition = NondeterministicTransitionFunction()
>>> transition.add_transition(State(0), Symbol("a"), State(1))
>>> transition.get_number_transitions()
1
is_deterministic()[source]

Whether the transition function is deterministic

Returns

is_deterministic – Whether the function is deterministic

Return type

bool

Examples

>>> transition = NondeterministicTransitionFunction()
>>> transition.add_transition(State(0), Symbol("a"), State(1))
>>> transition.is_deterministic()
True
remove_transition(s_from: pyformlang.finite_automaton.state.State, symb_by: pyformlang.finite_automaton.symbol.Symbol, s_to: pyformlang.finite_automaton.state.State) int[source]

Removes a transition to the function

Parameters
  • s_from (State) – The source state

  • symb_by (Symbol) – The transition symbol

  • s_to (State) – The destination state

Returns

done – 1 is the transition was found, 0 otherwise

Return type

int

Examples

>>> transition = NondeterministicTransitionFunction()
>>> transition.add_transition(State(0), Symbol("a"), State(1))
>>> transition.remove_transition(State(0), Symbol("a"), State(1))
to_dict()[source]

Get the dictionary representation of the transition function. The keys of the dictionary are the source nodes. The items are dictionaries where the keys are the symbols of the transitions and the items are the set of target nodes.

Returns

transition_dict – The transitions as a dictionary.

Return type

dict

class pyformlang.finite_automaton.State(value)[source]

A state in a finite automaton

Parameters

value (any) – The value of the state

Examples

>>> from pyformlang.finite_automaton import State
>>> State("A")
A
class pyformlang.finite_automaton.Symbol(value: Any)[source]

A symbol in a finite automaton

Parameters

value (any) – The value of the symbol

Examples

>>> from pyformlang.finite_automaton import Symbol
>>> Symbol("A")
A
class pyformlang.finite_automaton.TransitionFunction[source]

A transition function in a finite automaton.

This is a deterministic transition function.

_transitions

A dictionary which contains the transitions of a finite automaton

Type

dict

Examples

>>> transition = TransitionFunction()
>>> transition.add_transition(State(0), Symbol("a"), State(1))

Creates a transition function and adds a transition.

add_transition(s_from: pyformlang.finite_automaton.state.State, symb_by: pyformlang.finite_automaton.symbol.Symbol, s_to: pyformlang.finite_automaton.state.State) int[source]

Adds a new transition to the function

Parameters
  • s_from (State) – The source state

  • symb_by (Symbol) – The transition symbol

  • s_to (State) – The destination state

Returns

done – Always 1

Return type

int

Raises

DuplicateTransitionError – If the transition already exists

Examples

>>> transition = TransitionFunction()
>>> transition.add_transition(State(0), Symbol("a"), State(1))
get_edges()[source]

Gets the edges

Returns

edges – A generator of edges

Return type

generator of (State, Symbol, State)

get_number_transitions() int[source]

Gives the number of transitions describe by the deterministic function

Returns

n_transitions – The number of deterministic transitions

Return type

int

Examples

>>> transition = TransitionFunction()
>>> transition.add_transition(State(0), Symbol("a"), State(1))
>>> transition.get_number_transitions()
1
remove_transition(s_from: pyformlang.finite_automaton.state.State, symb_by: pyformlang.finite_automaton.symbol.Symbol, s_to: pyformlang.finite_automaton.state.State) int[source]

Removes a transition to the function

Parameters
  • s_from (State) – The source state

  • symb_by (Symbol) – The transition symbol

  • s_to (State) – The destination state

Returns

done – 1 is the transition was found, 0 otherwise

Return type

int

Examples

>>> transition = TransitionFunction()
>>> transition.add_transition(State(0), Symbol("a"), State(1))
>>> transition.remove_transition(State(0), Symbol("a"), State(1))
to_dict()[source]

Get the dictionary representation of the transition function. The keys of the dictionary are the source nodes. The items are dictionaries where the keys are the symbols of the transitions and the items are the set of target nodes.

Returns

transition_dict – The transitions as a dictionary.

Return type

dict