Regular Languages

Deterministic Finite Automaton

class maquinas.regular.dfa.DeterministicFiniteAutomaton(Q=[], sigma=[], q_0=None, A=[], delta={}, force=False)

Class for Deterministic Finite Automaton

Parameters
  • Q – Ordered set of states (default is empty).

  • sigma – Ordered set of symbols (default is empty).

  • q_0 – Initial state (default None).

  • A – Set of acceptor states (default is empty).

  • delta – List of transitions with the form tupla of tupla of q_i and a, and q_f (default is empty).

  • force (bool) – If True and states or symbols do not exists create them (default is False).

acceptor(q)

Checks if state is an acceptor state

Parameters

q – State or states

Returns

None

accepts(w)

Checks if string is accepted

Parameters

w – String

Returns

None

add_error_state(e_label='q_E')

Adds a error state (sink state)

Parameters

e_label – Label for the error state

Returns

None

add_next_state(initial=False)

Adds a state with a infered name based on the number of states q_max. If the name state is already defined it looks the following integer available.

Parameters
  • q – State or states

  • initial – Set state as a initial

Returns

Next state generated and integer

add_state(q, initial=False)

Adds a state

Parameters
  • q – State or states

  • initial – Set state as a initial

Returns

Indixes of state or states

add_symbol(a)

Adds a symbol

Parameters

a – Symbol

Returns

Indixes of symbol

add_transition(q_i, a, q_f, force=False, update=False)

Adds a transition

Parameters
  • q_i – Source state

  • a – Symbol

  • q_f – Destination state

Params force

Forces the creation of new symbols or states

Params update

If transition exists, updates it

Returns

None

autorename(start=0, avoid=[])

Autorenames the states with a patter of q_n, where n is a consicutive integer

Parameters
  • start – Staring numbering (default is 0)

  • avoid – List of labelings to avoid (default is empty)

Returns

None

delta(q, a)

Applies delta function

Parameters
  • q – Source state

  • a – Symbol

Returns

Destination state

delta_extended(q, w)

Applies delta extended function

Parameters
  • q – Source state

  • w – String

Returns

Destination state after processing the full string

delta_stepwise(w, q=None)

Applies a step of delta extended function

Parameters
  • w – String

  • q – Source state (default is initial state)

Returns

Tuple with state of precessing at step, consisting of: destination state, procesed symbol and processed string

get_aceptors()

Gets aceptors states

Returns

States

get_initial_state()

Gets an initial state

Returns

State

get_transition(q, a)

Gets the destintion state or states for state and symbol

Parameters
  • nq – Source state

  • na – Symbol

Returns

Destination state or states

graph(q_c={}, a_c={}, q_prev={}, symbols={}, states={}, format='svg', dpi='60.0', string=None, **args)

Graphs DFA

Parameters
  • q_c – Set of current states to be highlited (default is empty)

  • a_c – Set of current symbols to be highlited (default is empty)

  • q_prev – Set of previos states to be highlited (default is empty)

  • symbols – Replacements of the symbols to show (default is empty)

  • states – Replacements of the states to show (default is empty)

  • format – Format of image (default is svg)

  • dpi – Resolution of image (default is “60.0”)

  • string – Label of string being analysed (default is None)

Returns

Returns Digraph object from graphviz

items()

Iterator over the transitions

Returns

Yeilds a tuple transition

print_summary(symbols={}, states={}, **args)

Print a summary of the AF

Parameters
  • symbols – Replacements of the symbols to print

  • states – Replacements of the states to print

  • args – Parameters for the print

Returns

None

print_transitions(w, symbols={}, states={}, **args)

Print a transition for the string w

Parameters
  • w – Replacements of the symbols to print

  • states – Replacements of the states to print

  • args – Parameters for the print

Returns

None

reachable_states()

Calculate the set of states which are reacheble

Returns

List of reachable states

remove_sink_states()

Remove states that do no go to any place

Returns

None

remove_states(states)

Remove states

Parameters

states – List of states to remove

Returns

None

remove_unreachable()

Removes the set of states which are unreacheble

Returns

List of unreachable states

replace_state(old, new)

Replace a state

Parameters
  • old – State to be replaced

  • new – State to replace with

Returns

None

replace_symbol(old, new)

Replace a symbol

Parameters
  • old – Symbol to be replaced

  • new – Symbol to replace with

Returns

None

save_file(filename='machine.txt', order_Q=None, order_sigma=None)

Saves a file

Parameters
  • filename – Name of filename (default is machine.txt)

  • order_Q – Order to print states

  • order_sigma – Order to print vocabulary

Returns

None

save_gif(w, filename='maquina.gif', symbols={}, states={}, dpi='90', show=False, loop=0, duration=500)

Saves an animation of machine

Parameters
  • w – String to analysed during animation

  • filename – Name of gif (default is “maquina.gif”)

  • symbols – Replacements of the symbols to show (default is empty)

  • states – Replacements of the states to show (default is empty)

  • dpi – Resolution of image (default is “90.0”)

  • show – In interactive mode return gif

  • loop – Number of loops in annimation, cero is forever (default is 0)

  • duration – Duration in msegs among steps (default is 500)

Returns

None or HTML for Ipython

save_img(filename, q_c={}, a_c={}, q_prev={}, symbols={}, states={}, format='svg', dpi='60.0', string=None)

Saves machine as an image

Parameters
  • filename – Filename of image

  • q_c – Set of current states to be highlited (default is empty)

  • a_c – Set of current symbols to be highlited (default is empty)

  • q_prev – Set of previos states to be highlited (default is empty)

  • symbols – Replacements of the symbols to show (default is empty)

  • states – Replacements of the states to show (default is empty)

  • format – Format of image (default is svg)

  • dpi – Resolution of image (default is “60.0”)

  • string – Label of string being analysed (default is None)

Returns

None

set_aceptors(A, force=False)

Sets aceptors states

Parameters
  • A – States

  • force – If not defined it creates it (default is False)

Returns

None

set_initial_state(q, force=False)

Sets an initial state

Parameters
  • q – State

  • force – If not defined it creates it (default is False)

Returns

None

states()

Gets states

Returns

States of machine

Return type

list

stepStatus(status)

Gives a step and calculates new status for Simulation

Parameters

Status – Status

Returns

None

summary(symbols={}, states={})

Produces a summary of the AF

Parameters
  • symbols – Replacements of the symbols to print

  • states – Replacements of the states to print

Returns

List with summary

symbols()

Gets symbols

Returns

Symbols of machine

Return type

list

table(symbols={}, states={}, q_order=None, s_order=None, empty_transition='', color_final='#32a852')

Creates an HTML object for the table of the DFA

Parameters
  • symbols – Replacements of the symbols to show (default is empty)

  • states – Replacements of the states to show (default is empty)

  • q_order – Order to use for state

  • s_order – Order to use for symbols

  • empty_transition – Symbol to print for empty transitin (default is “”)

  • color_final – RGB string for color of final state (default is “#32a852”)

Returns

Display object for IPython

to_string(order_Q=None, order_sigma=None)

Creates a string

Parameters
  • order_Q – Order to print states

  • order_sigma – Order to print vocabulary

Returns

None

unreachable_states()

Calculate the set of states which are unreacheble

Returns

List of unreachable states

Non Deterministic Finite Automaton

class maquinas.regular.ndfa.NonDeterministicFiniteAutomaton(Q=[], sigma=[], q_0=None, A=[], delta={}, force=False)

Class for Deterministic Finite Automaton

Parameters
  • Q – Ordered set of states (default is empty).

  • sigma – Ordered set of symbols (default is empty).

  • q_0 – Initial state (default None).

  • A – Set of acceptor states (default is empty).

  • delta – List of transitions with the form tupla of tupla of q_i and a, and q_f (default is empty).

  • force (bool) – If True and states or symbols do not exists create them (default is False).

acceptor(q)

Checks if state is an acceptor state

Parameters

q – State or states

Returns

None

accepts(w)

Checks if string is accepted

Parameters

w – String

Returns

None

add_error_state(e_label='q_E')

Adds a error state (sink state)

Parameters

e_label – Label for the error state

Returns

None

add_next_state(initial=False)

Adds a state with a infered name based on the number of states q_max. If the name state is already defined it looks the following integer available.

Parameters
  • q – State or states

  • initial – Set state as a initial

Returns

Next state generated and integer

add_state(q, initial=False)

Adds a state

Parameters
  • q – State or states

  • initial – Set state as a initial

Returns

Indixes of state or states

add_symbol(a)

Adds a symbol

Parameters

a – Symbol

Returns

Indixes of symbol

add_transition(q_i, a, q_f, force=False, update=False)

Adds a transition

Parameters
  • q_i – Source state

  • a – Symbol

  • q_f – Destination state

Params force

Forces the creation of new symbols or states

Params update

If transition exists, updates it

Returns

None

autorename(start=0, avoid=[])

Autorenames the states with a patter of q_n, where n is a consicutive integer

Parameters
  • start – Staring numbering (default is 0)

  • avoid – List of labelings to avoid (default is empty)

Returns

None

delta(q, a)

Applies delta function

Parameters
  • q – Source state

  • a – Symbol

Returns

Set of destination state

delta_extended(q, w)

Applies delta extended function

Parameters
  • q – Source state

  • w – String

Returns

Set of destination states after processing the full string

delta_stepwise(w, q=None)

Applies a step of delta extended function

Parameters
  • w – String

  • q – Source state (default is initial state)

Returns

Tuple with state of precessing at step, consisting of: set of destination states, procesed symbol and processed string

get_aceptors()

Gets aceptors states

Returns

States

get_initial_state()

Gets an initial state

Returns

State

get_transition(q, a)

Gets the destintion state or states for state and symbol

Parameters
  • nq – Source state

  • na – Symbol

Returns

Destination state or states

graph(q_c={}, a_c={}, q_prev={}, symbols={}, states={}, format='svg', dpi='60.0', string=None, **args)

Graphs NDFA

Parameters
  • q_c – Set of current states to be highlited (default is empty)

  • a_c – Set of current symbols to be highlited (default is empty)

  • q_prev – Set of previos states to be highlited (default is empty)

  • symbols – Replacements of the symbols to show (default is empty)

  • states – Replacements of the states to show (default is empty)

  • format – Format of image (default is svg)

  • dpi – Resolution of image (default is “60.0”)

  • string – Label of string being analysed (default is None)

Returns

Returns Digraph object from graphviz

items()

Iterator over the transitions

Returns

Yeilds a tuple transition

print_summary(symbols={}, states={}, **args)

Print a summary of the AF

Parameters
  • symbols – Replacements of the symbols to print

  • states – Replacements of the states to print

  • args – Parameters for the print

Returns

None

print_transitions(w, symbols={}, states={}, **args)

Print a transition for the string w

Parameters
  • w – Replacements of the symbols to print

  • states – Replacements of the states to print

  • args – Parameters for the print

Returns

None

reachable_states()

Calculate the set of states which are reacheble

Returns

List of reachable states

remove_sink_states()

Remove states that do no go to any place

Returns

None

remove_states(states)

Remove states

Parameters

states – List of states to remove

Returns

None

remove_unreachable()

Removes the set of states which are unreacheble

Returns

List of unreachable states

replace_state(old, new)

Replace a state

Parameters
  • old – State to be replaced

  • new – State to replace with

Returns

None

replace_symbol(old, new)

Replace a symbol

Parameters
  • old – Symbol to be replaced

  • new – Symbol to replace with

Returns

None

save_file(filename='machine.txt', order_Q=None, order_sigma=None)

Saves a file

Parameters
  • filename – Name of filename (default is machine.txt)

  • order_Q – Order to print states

  • order_sigma – Order to print vocabulary

Returns

None

save_gif(w, filename='maquina.gif', symbols={}, states={}, dpi='90', show=False, loop=0, duration=500)

Saves an animation of machine

Parameters
  • w – String to analysed during animation

  • filename – Name of gif (default is “maquina.gif”)

  • symbols – Replacements of the symbols to show (default is empty)

  • states – Replacements of the states to show (default is empty)

  • dpi – Resolution of image (default is “90.0”)

  • show – In interactive mode return gif

  • loop – Number of loops in annimation, cero is forever (default is 0)

  • duration – Duration in msegs among steps (default is 500)

Returns

None or HTML for Ipython

save_img(filename, q_c={}, a_c={}, q_prev={}, symbols={}, states={}, format='svg', dpi='60.0', string=None)

Saves machine as an image

Parameters
  • filename – Filename of image

  • q_c – Set of current states to be highlited (default is empty)

  • a_c – Set of current symbols to be highlited (default is empty)

  • q_prev – Set of previos states to be highlited (default is empty)

  • symbols – Replacements of the symbols to show (default is empty)

  • states – Replacements of the states to show (default is empty)

  • format – Format of image (default is svg)

  • dpi – Resolution of image (default is “60.0”)

  • string – Label of string being analysed (default is None)

Returns

None

set_aceptors(A, force=False)

Sets aceptors states

Parameters
  • A – States

  • force – If not defined it creates it (default is False)

Returns

None

set_initial_state(q, force=False)

Sets an initial state

Parameters
  • q – State

  • force – If not defined it creates it (default is False)

Returns

None

states()

Gets states

Returns

States of machine

Return type

list

stepStatus(status)

Gives a step and calculates new status for Simulation

Parameters

Status – Status

Returns

None

summary(symbols={}, states={})

Produces a summary of the AF

Parameters
  • symbols – Replacements of the symbols to print

  • states – Replacements of the states to print

Returns

List with summary

symbols()

Gets symbols

Returns

Symbols of machine

Return type

list

table(symbols={}, states={}, q_order=None, s_order=None, color_final='#32a852', empty_symbol='∅')

Creates an HTML object for the table of the NDFA

Parameters
  • symbols – Replacements of the symbols to show (default is empty)

  • states – Replacements of the states to show (default is empty)

  • q_order – Order to use for states

  • s_order – Order to use for symbols

  • color_final – RGB string for color of final state (default is “#32a852”)

  • empy_symbol – Symbol to be used to display in empty cells (defualt is “∅”)

Returns

Display object for IPython

to_string(order_Q=None, order_sigma=None)

Creates a string

Parameters
  • order_Q – Order to print states

  • order_sigma – Order to print vocabulary

Returns

None

unreachable_states()

Calculate the set of states which are unreacheble

Returns

List of unreachable states

Non Deterministic Finite Automaton with epsilon

class maquinas.regular.ndfa_e.NonDeterministicFiniteAutomaton_epsilon(Q=[], sigma=[], q_0=None, A=[], delta=[], force=False)

Class for Deterministic Finite Automaton

Parameters
  • Q – Ordered set of states (default is empty).

  • sigma – Ordered set of symbols (default is empty).

  • q_0 – Initial state (default None).

  • A – Set of acceptor states (default is empty).

  • delta – List of transitions with the form tupla of tupla of q_i and a, and q_f (default is empty).

  • force (bool) – If True and states or symbols do not exists create them (default is False).

acceptor(q)

Checks if state is an acceptor state

Parameters

q – State or states

Returns

None

accepts(w)

Checks if string is accepted

Parameters

w – String

Returns

None

add_error_state(e_label='q_E')

Adds a error state (sink state)

Parameters

e_label – Label for the error state

Returns

None

add_next_state(initial=False)

Adds a state with a infered name based on the number of states q_max. If the name state is already defined it looks the following integer available.

Parameters
  • q – State or states

  • initial – Set state as a initial

Returns

Next state generated and integer

add_state(q, initial=False)

Adds a state

Parameters
  • q – State or states

  • initial – Set state as a initial

Returns

Indixes of state or states

add_symbol(a)

Adds a symbol

Parameters

a – Symbol

Returns

Indixes of symbol

add_transition(q_i, a, q_f, force=False, update=False)

Adds a transition

Parameters
  • q_i – Source state

  • a – Symbol

  • q_f – Destination state

Params force

Forces the creation of new symbols or states

Params update

If transition exists, updates it

Returns

None

autorename(start=0, avoid=[])

Autorenames the states with a patter of q_n, where n is a consicutive integer

Parameters
  • start – Staring numbering (default is 0)

  • avoid – List of labelings to avoid (default is empty)

Returns

None

concat(other, label_a='ᴬ', label_b='ᴮ')

Concatenates of this NDFA_e with other NDFA-e

Parameters
  • other – Other NDFA-e

  • label_a – Label to append to states of this NDFA-e (default is “ᴬ”)

  • label_b – Label to append to states of other NDFA-e (default is “ᴮ”)

Returns

Returns NDFA resulting of the concatenation of this an another NDFA-e

delta(q, a)

Applies delta function

Parameters
  • q – Source state

  • a – Symbol

Returns

Destination state

delta_extended(q, w)

Applies delta extended function

Parameters
  • q – Source state

  • w – String

Returns

Destination state after processing the full string

delta_stepwise(w, q=None)

Applies a step of delta extended function

Parameters
  • w – String

  • q – Source state (default is initial state)

Returns

Tuple with state of precessing at step, consisting of: destination state, procesed symbol and processed string

expansion_epsilon(qs)

Applies expansion by epsilon in a set of states

Parameters

qs – Set of states

Returns

Set of reachable states from qs

get_aceptors()

Gets aceptors states

Returns

States

get_initial_state()

Gets an initial state

Returns

State

get_transition(q, a)

Gets the destintion state or states for state and symbol

Parameters
  • nq – Source state

  • na – Symbol

Returns

Destination state or states

graph(q_c={}, a_c={}, q_prev={}, symbols={}, states={}, format='svg', dpi='60.0', string=None, **args)

Graphs NDFA_e

Parameters
  • q_c – Set of current states to be highlited (default is empty)

  • a_c – Set of current symbols to be highlited (default is empty)

  • q_prev – Set of previos states to be highlited (default is empty)

  • symbols – Replacements of the symbols to show (default is empty)

  • states – Replacements of the states to show (default is empty)

  • format – Format of image (default is svg)

  • dpi – Resolution of image (default is “60.0”)

  • string – Label of string being analysed (default is None)

Returns

Returns Digraph object from graphviz

items()

Iterator over the transitions

Returns

Yeilds a tuple transition

kleene(label='ᴬ')

Applies Kleene closure to this NDFA_e

Parameters

label – Label to append to states of this NDFA-e (default is “ᴬ”)

Returns

Returns NDFA resulting of the application of Kleen closure to this NDFA-e

print_summary(symbols={}, states={}, **args)

Print a summary of the AF

Parameters
  • symbols – Replacements of the symbols to print

  • states – Replacements of the states to print

  • args – Parameters for the print

Returns

None

print_transitions(w, symbols={}, states={}, **args)

Print a transition for the string w

Parameters
  • w – Replacements of the symbols to print

  • states – Replacements of the states to print

  • args – Parameters for the print

Returns

None

reachable_states()

Calculate the set of states which are reacheble

Returns

List of reachable states

remove_sink_states()

Remove states that do no go to any place

Returns

None

remove_states(states)

Remove states

Parameters

states – List of states to remove

Returns

None

remove_unreachable()

Removes the set of states which are unreacheble

Returns

List of unreachable states

replace_state(old, new)

Replace a state

Parameters
  • old – State to be replaced

  • new – State to replace with

Returns

None

replace_symbol(old, new)

Replace a symbol

Parameters
  • old – Symbol to be replaced

  • new – Symbol to replace with

Returns

None

save_file(filename='machine.txt', order_Q=None, order_sigma=None)

Saves a file

Parameters
  • filename – Name of filename (default is machine.txt)

  • order_Q – Order to print states

  • order_sigma – Order to print vocabulary

Returns

None

save_gif(w, filename='maquina.gif', symbols={}, states={}, dpi='90', show=False, loop=0, duration=500)

Saves an animation of machine

Parameters
  • w – String to analysed during animation

  • filename – Name of gif (default is “maquina.gif”)

  • symbols – Replacements of the symbols to show (default is empty)

  • states – Replacements of the states to show (default is empty)

  • dpi – Resolution of image (default is “90.0”)

  • show – In interactive mode return gif

  • loop – Number of loops in annimation, cero is forever (default is 0)

  • duration – Duration in msegs among steps (default is 500)

Returns

None or HTML for Ipython

save_img(filename, q_c={}, a_c={}, q_prev={}, symbols={}, states={}, format='svg', dpi='60.0', string=None)

Saves machine as an image

Parameters
  • filename – Filename of image

  • q_c – Set of current states to be highlited (default is empty)

  • a_c – Set of current symbols to be highlited (default is empty)

  • q_prev – Set of previos states to be highlited (default is empty)

  • symbols – Replacements of the symbols to show (default is empty)

  • states – Replacements of the states to show (default is empty)

  • format – Format of image (default is svg)

  • dpi – Resolution of image (default is “60.0”)

  • string – Label of string being analysed (default is None)

Returns

None

set_aceptors(A, force=False)

Sets aceptors states

Parameters
  • A – States

  • force – If not defined it creates it (default is False)

Returns

None

set_initial_state(q, force=False)

Sets an initial state

Parameters
  • q – State

  • force – If not defined it creates it (default is False)

Returns

None

states()

Gets states

Returns

States of machine

Return type

list

stepStatus(status)

Gives a step and calculates new status for Simulation

Parameters

Status – Status

Returns

None

summary(symbols={}, states={})

Produces a summary of the AF

Parameters
  • symbols – Replacements of the symbols to print

  • states – Replacements of the states to print

Returns

List with summary

symbols()

Gets symbols

Returns

Symbols of machine

Return type

list

table(symbols={}, states={}, q_order=None, s_order=None, color_final='#32a852', empty_symbol='∅')

Creates an HTML object for the table of the DFA

Parameters
  • symbols – Replacements of the symbols to show (default is empty)

  • states – Replacements of the states to show (default is empty)

  • q_order – Order to use for states

  • s_order – Order to use for symbols

  • color_final – RGB string for color of final state (default is “#32a852”)

Returns

Display object for IPython

to_string(order_Q=None, order_sigma=None)

Creates a string

Parameters
  • order_Q – Order to print states

  • order_sigma – Order to print vocabulary

Returns

None

union(other, label_a='ᴬ', label_b='ᴮ')

Unites this NDFA_e with other NDFA-e

Parameters
  • other – Other NDFA-e

  • label_a – Label to append to states of this NDFA-e (default is “ᴬ”)

  • label_b – Label to append to states of other NDFA-e (default is “ᴮ”)

Returns

Returns NDFA resultinf of the union of this an another NDFA-e

unreachable_states()

Calculate the set of states which are unreacheble

Returns

List of unreachable states

Regular Grammar

Reductions

maquinas.regular.reductions.dfa2ndfa(dfa, rename=True, remove_sink=True)

Reduces a DFA to a NDFA

Parameters
  • dfa – DFA to reduce

  • raname – Rename states after reduction

  • remove_sink – Remove sink states after reduction

maquinas.regular.reductions.dfa2ndfa_e(dfa, rename=True, remove_sink=True)

Reduces a DFA to a NDFA-e

Parameters
  • dfa – DFA to reduce

  • raname – Rename states after reduction

  • remove_sink – Remove sink states after reduction

maquinas.regular.reductions.ndfa2dfa(ndfa, order=None, rename=True, remove_sink=True)

Reduces a NDFA to a DFA

Parameters
  • ndfa – NDFA to reduce

  • order – Order for states

  • raname – Rename states after reduction

  • remove_sink – Remove sink states after reduction

maquinas.regular.reductions.ndfa2ndfa_e(ndfa, rename=True, remove_sink=True)

Reduces a NDFA to a NDFA-e

Parameters
  • dfa – NDFA to reduce

  • raname – Rename states after reduction

  • remove_sink – Remove sink states after reduction

maquinas.regular.reductions.ndfa_e2dfa(ndfa_e, rename=True, remove_sink=True)

Reduces a NDFA-e to a DFA

Parameters
  • dfa – NDFA-e to reduce

  • raname – Rename states after reduction

  • remove_sink – Remove sink states after reduction

maquinas.regular.reductions.ndfa_e2ndfa(ndfa_e, rename=True, remove_sink=True)

Reduces a NDFA-e to a NDFA

Parameters
  • ndfa_e – NDFA-e to reduce

  • raname – Rename states after reduction

  • remove_sink – Remove sink states after reduction

Minimization

maquinas.regular.minimization.minimization_hopcroft(dfa, rename=True, remove_sink=True)

Minimization of a DFA through the Hofproft method, for more info checK:

From http://www-igm.univ-mlv.fr/~berstel/Exposes/2009-06-08MinimisationLiege.pdf

Parameters
  • dfa – DFA to minimize

  • rename – If true it will rename states after minimization process

  • remove_sink – If true it will remove sink states