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