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: AbstractSet[State] = None, input_symbols: AbstractSet[Symbol] = None, transition_function: TransitionFunction = None, start_state: State = None, final_states: AbstractSet[State] = None)[source]

Represents a deterministic finite automaton

This class represents a deterministic finite automaton.

Parameters:

statesset of State, optional: A finite set of states
input_symbolsset of Symbol, optional: A finite set of input symbols
transition_functionTransitionFunction, optional: Takes as arguments a state and an input symbol and returns a state.
start_stateState, optional: A start state, element of states
final_statesset 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[Any]) → bool[source]

Checks whether the dfa accepts a given word

Parameters:

worditerable of Symbol: A sequence of input symbols

Returns:

is_acceptedbool: Whether the word is accepted or not

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: Any) → int[source]

Set an initial state

Parameters:

stateState: The new initial state

Returns:

doneint: 1 is correctly added

Examples

>>> dfa = DeterministicFiniteAutomaton()
>>> dfa.add_start_state(0)

copy() → DeterministicFiniteAutomaton[source]

Copies the current DFA

Returns:

enfaDeterministicFiniteAutomaton: A copy of the current DFA

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_deterministicbool: Whether the automaton is deterministic

Examples

>>> dfa = DeterministicFiniteAutomaton()
>>> dfa.is_deterministic()
True

is_equivalent_to(other)[source]

Check whether two automata are equivalent

Parameters:

otherFiniteAutomaton: A sequence of input symbols

Returns:

are_equivalentbool: Whether the two automata are equivalent or not

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() → DeterministicFiniteAutomaton[source]

Minimize the current DFA

Returns:

dfaDeterministicFiniteAutomaton: The minimal DFA

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: Any) → int[source]

remove an initial state

Parameters:

stateState: The new initial state

Returns:

doneint: 1 is correctly added

Examples

>>> dfa = DeterministicFiniteAutomaton()
>>> dfa.add_start_state(0)
>>> dfa.remove_start_state(0)

property start_state: State: The start state

to_deterministic() → DeterministicFiniteAutomaton[source]

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

Returns:

dfaDeterministicFiniteAutomaton: A dfa equivalent to the current nfa

Examples

>>> dfa0 = DeterministicFiniteAutomaton()
>>> dfa1 = dfa0.to_deterministic()
>>> dfa0.is_equivalent_to(dfa1)
True

exception pyformlang.finite_automaton.DuplicateTransitionError(s_from: State, symb_by: Symbol, s_to: State, s_to_old: State)[source]

Signals a duplicated transition

Parameters:

s_fromState: The source state
symb_bySymbol: The transition symbol
s_toState: The wanted new destination state
s_to_oldState: The old destination state

class pyformlang.finite_automaton.Epsilon[source]

An epsilon transition

Examples

>>> epsilon = Epsilon()

class pyformlang.finite_automaton.EpsilonNFA(states: AbstractSet[State] = None, input_symbols: AbstractSet[Symbol] = None, transition_function: NondeterministicTransitionFunction = None, start_state: AbstractSet[State] = None, final_states: AbstractSet[State] = None)[source]

Represents an epsilon NFA

Parameters:

statesset of State, optional: A finite set of states
input_symbolsset of Symbol, optional: A finite set of input symbols
transition_functionNondeterministicTransitionFunction, optional: Takes as arguments a state and an input symbol and returns a state.
start_stateset of State, optional: A start state, element of states
final_statesset 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[Any]) → bool[source]

Checks whether the epsilon nfa accepts a given word

Parameters:

worditerable of Symbol: A sequence of input symbols

Returns:

is_acceptedbool: Whether the word is accepted or not

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() → EpsilonNFA[source]

Copies the current Epsilon NFA

Returns:

enfaEpsilonNFA: A copy of the current Epsilon NFA

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: Any) → Set[State][source]

Compute the epsilon closure of a state

Parameters:

stateState: The source state

Returns:

statesset of State: The epsilon closure of the source 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[Any]) → Set[State][source]

Compute the epsilon closure of a collection of states

Parameters:

statesiterable of State: The source states

Returns:

statesset of State: The epsilon closure of the source 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() → EpsilonNFA[source]

Get the complement of the current Epsilon NFA

Equivalent to:

>>> -automaton

Returns:

enfaEpsilonNFA: A complement automaton

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: EpsilonNFA) → EpsilonNFA[source]

Compute the difference with another Epsilon NFA

Equivalent to:

>>> automaton0 - automaton1

Parameters:

otherEpsilonNFA: The other Epsilon NFA

Returns:

enfaEpsilonNFA: The difference with the other epsilon NFA

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: EpsilonNFA) → EpsilonNFA[source]

Computes the intersection of two Epsilon NFAs

Equivalent to:

>>> automaton0 and automaton1

Parameters:

otherEpsilonNFA: The other Epsilon NFA

Returns:

enfaEpsilonNFA: The intersection of the two Epsilon NFAs

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_deterministicbool: Whether the automaton is deterministic

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_emptybool: Whether the language is empty or not

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:

dfaDeterministicFiniteAutomaton: The minimal DFA

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

remove_epsilon_transitions() → NondeterministicFiniteAutomaton[source]

Removes the epsilon transitions from the automaton

Returns:

dfaNondeterministicFiniteAutomaton: A non-deterministic finite automaton equivalent to the current nfa, with no epsilon transition

reverse() → EpsilonNFA[source]

Compute the reversed EpsilonNFA

Equivalent to:: >> ~automaton

Returns:

enfaEpsilonNFA: The reversed automaton

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:

dfaDeterministicFiniteAutomaton: A dfa equivalent to the current nfa

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:

regexRegex: A regular expression equivalent to the current Epsilon NFA

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

Attributes:

_statesset of State, optional: A finite set of states
_input_symbolsset of Symbol, optional: A finite set of input symbols
_transition_functionNondeterministicTransitionFunction , optional: Takes as arguments a state and an input symbol and returns a state.
_start_stateset of State, optional: A start state, element of states
_final_statesset of State, optional: A set of final or accepting states. It is a subset of states.

add_final_state(state: Any) → int[source]

Adds a new final state

Parameters:

stateState: A new final state

Returns:

doneint: 1 is correctly added

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: Any) → int[source]

Set an initial state

Parameters:

stateState: The new initial state

Returns:

doneint: 1 is correctly added

Examples

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

add_symbol(symbol: Symbol)[source]

Add a symbol

Parameters:

symbolSymbol: The symbol

Examples

>>> enfa = EpsilonNFA()
>>> enfa.add_symbol("a")

add_transition(s_from: Any, symb_by: Any, s_to: Any) → int[source]

Adds a transition to the nfa

Parameters:

s_fromState: The source state
symb_bySymbol: The transition symbol
s_toState: The destination state

Returns:

doneint: Always 1

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_listlist 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:

doneint: Always 1

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:

enfa: A epsilon nondeterministic finite automaton read from the graph

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_accepted_words(max_length: int | None = None) → Iterable[List[Symbol]][source]: Gets words accepted by the finite automaton.

get_number_transitions() → int[source]

Gives the number of transitions

Returns:

n_transitionsint: The number of deterministic transitions

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_acyclicbool: Whether the automaton is acyclic or not

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_equivalentbool: Whether the two automata are equivalent or not

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: State) → bool[source]

Checks if a state is final

Parameters:

stateState: The state to check

Returns:

is_finalbool: Whether the state is final or not

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: State) → int[source]

Remove a final state

Parameters:

stateState: A final state to remove

Returns:

doneint: 0 if it was not a final state, 1 otherwise

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: State) → int[source]

remove an initial state

Parameters:

stateState: The new initial state

Returns:

doneint: 1 is correctly added

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: State, symb_by: Symbol, s_to: State) → int[source]

Remove a transition of the nfa

Parameters:

s_fromState: The source state
symb_bySymbol: The transition symbol
s_toState: The destination state

Returns:

doneint: 1 if the transition existed, 0 otherwise

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:

statesset of State: The states

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_dictdict: The transitions as a dictionary.

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() → 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:

fstFST: The equivalent FST

Examples

>>> enfa = EpsilonNFA()
>>> fst = enfa.to_fst()
>>> fst.states
{}

to_networkx() → MultiDiGraph[source]

Transform the current automaton into a networkx graph

Returns:

graphnetworkx.MultiDiGraph: A networkx MultiDiGraph representing the automaton

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:

filenamestr: 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: AbstractSet[State] = None, input_symbols: AbstractSet[Symbol] = None, transition_function: NondeterministicTransitionFunction = None, start_state: AbstractSet[State] = None, final_states: AbstractSet[State] = None)[source]

Represents a nondeterministic finite automaton

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

Parameters:

statesset of State, optional: A finite set of states
input_symbolsset of Symbol, optional: A finite set of input symbols
transition_functionNondeterministicTransitionFunction , optional: Takes as arguments a state and an input symbol and returns a state.
start_stateState, optional: A start state, element of states
final_statesset 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[Any]) → bool[source]

Checks whether the nfa accepts a given word

Parameters:

worditerable of Symbol: A sequence of input symbols

Returns:

is_acceptedbool: Whether the word is accepted or not

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: Any, symb_by: Any, s_to: Any) → int[source]

Adds a transition to the nfa

Parameters:

s_fromState: The source state
symb_bySymbol: The transition symbol
s_toState: The destination state

Returns:

doneint: Always 1

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_deterministicbool: Whether the automaton is deterministic

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:

dfaDeterministicFiniteAutomaton: A dfa equivalent to the current nfa

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: State, symb_by: Symbol, s_to: State) → int[source]

Adds a new transition to the function

Parameters:

s_fromState: The source state
symb_bySymbol: The transition symbol
s_toState: The destination state

Returns:

doneint: Always 1

Examples

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

get_edges()[source]

Gets the edges

Returns:

edgesgenerator of (State, Symbol, State): A generator of edges

get_number_transitions() → int[source]

Gives the number of transitions describe by the function

Returns:

n_transitionsint: The number of transitions

Examples

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

get_transitions_from(state_from: State) → Iterable[Tuple[Symbol, State]][source]: Gets transitions from the given state

is_deterministic()[source]

Whether the transition function is deterministic

Returns:

is_deterministicbool: Whether the function is deterministic

Examples

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

remove_transition(s_from: State, symb_by: Symbol, s_to: State) → int[source]

Removes a transition to the function

Parameters:

s_fromState: The source state
symb_bySymbol: The transition symbol
s_toState: The destination state

Returns:

doneint: 1 is the transition was found, 0 otherwise

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_dictdict: The transitions as a dictionary.

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

A state in a finite automaton

Parameters:

valueany: 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:

valueany: 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.

Attributes:

_transitionsdict: A dictionary which contains the transitions of a finite automaton

Examples

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

Creates a transition function and adds a transition.

add_transition(s_from: Any, symb_by: Any, s_to: Any) → int[source]

Adds a new transition to the function

Parameters:

s_fromState: The source state
symb_bySymbol: The transition symbol
s_toState: The destination state

Returns:

doneint: Always 1

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:

edgesgenerator of (State, Symbol, State): A generator of edges

get_number_transitions() → int[source]

Gives the number of transitions describe by the deterministic function

Returns:

n_transitionsint: The number of deterministic transitions

Examples

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

get_transitions_from(state_from: State) → Iterable[Tuple[Symbol, State]][source]: Gets transitions from the given state

remove_transition(s_from: State, symb_by: Symbol, s_to: State) → int[source]

Removes a transition to the function

Parameters:

s_fromState: The source state
symb_bySymbol: The transition symbol
s_toState: The destination state

Returns:

doneint: 1 is the transition was found, 0 otherwise

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_dictdict: The transitions as a dictionary.

Finite Automaton

pyformlang.finite_automaton

Available Classes

`pyformlang.finite_automaton`