FAdo: Tools for Language Models Manipulation
Authors: Rogério Reis & Nelma Moreira
The support of transducers and all its operations, is a collaborativejoint work with Stavros Konstantinidis (St. Mary’s University, Halifax, NS, Canada) (http://cs.smu.ca/~stavros/).
Contributions by
|
|
Page of the project: http://fado.dcc.fc.up.pt.
Version: 1.2
Copyright: 1999-2014 Rogério Reis & Nelma Moreira<EMAIL_ADDRESS>Faculdade de Ciências da Universidade do Porto
Centro de Matemática da Universidade do Porto
Licence:
This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
The FAdo system aims to provide an open source extensible high-performance software library for the symbolic manipulation of automata and other models of computation.
To allow high-level programming with complex data structures, easy prototyping of algorithms, and portability (to use in computer grid systems for example), are its main features. Our main motivation is the theoretical and experimental research, but we have also in mind the construction of a pedagogical tool for teaching automata theory and formal languages.
It currently includes most standard operations for the manipulation of regular languages. Regular languages can be represented by regular expressions (regexp) or finite automata, among other formalisms. Finite automata may be deterministic (DFA), non-deterministic (NFA) or generalized (GFA). In FAdo these representations are implemented as Python classes.
Elementary regular languages operations as union, intersection, concatenation, complementation and reverse are implemented for each class. Also several combined operations are available for specific models.
Several conversions between these representations are implemented:
Special methods for finite languages are available:
Several methods for transducers in standard form (SFT) are available:
A language property is a set of languages. Given a property specified by a transducer, several language tests are possible.
Finite automata manipulation.
Deterministic and non-deterministic automata manipulation, conversion and evaluation.
Bases: common.Drawable
Base class for Finite Automata.
| Variables: |
|
|---|
Note
This is just an abstract class. Not to be used directly!!
A new state is added to the already defined set of final states.
| Parameters: | stateindex (int) – index of the new final state |
|---|
Adds a new symbol to the alphabet.
| Parameters: | sym (str) – symbol to be added |
|---|---|
| Raises DFAepsilonRedefenition: | |
| if sym is Epsilon |
Note
Adds a new state to an FA. If no name is given a new name is created.
| Parameters: | name (object) – Name of the state to be added |
|---|---|
| Returns: | Current number of states (the new state index) |
| Return type: | int |
| Raises DuplicateName: | |
| if a state with that name already exists |
A simple literate invocation of __and__
| Parameters: | other – the other FA |
|---|
New in version 0.9.6.
Evaluates the size of FA transitionwise
| Returns: | the number of transitions |
|---|---|
| Return type: | int |
Changed in version 1.0.
Deletes a state from the final states list
| Parameters: | st (int) – state to be marked as not final |
|---|
Remove the given state and the transitions related with that state.
| Parameters: | sti (int) – index of the state to be removed |
|---|---|
| Raises DFAstateUnknown: | |
| if state index does not exist |
Another simple literate invocation of __or__
| Parameters: | other – the other FA |
|---|
New in version 0.9.6.
A dot representation
| Parameters: | |
|---|---|
| Returns: | the dot representation |
| Return type: | str |
New in version 0.9.6.
Changed in version 0.9.8.
Eliminates dead state name (common.DeadName) renaming the state
Attention
works inplace
New in version 1.2.
Test equivalence
| Parameters: | other – the other automata |
|---|---|
| Return type: | bool |
New in version 0.9.6.
Tests if a state is final
| Parameters: | state (int) – state index |
|---|---|
| Return type: | bool |
Tests if al the states in a set are final
| Parameters: | states (set) – set of state indexes |
|---|---|
| Return type: | bool |
New in version 1.0.
Checks if a state index pertains to an FA
| Parameters: | st (int) – index of the state |
|---|---|
| Return type: | bool |
Converts a list of stateNames into a set of stateIndexes.
| Parameters: | lstn (list) – list of names |
|---|---|
| Returns: | the list of state indexes |
| Return type: | Set of int |
| Raises DFAstateUnknown: | |
| if a state name is unknown |
Tests if a state is initial
| Parameters: | state (int) – state index |
|---|---|
| Return type: | bool |
The set of initial states
| Returns: | the set of the initial states |
|---|---|
| Return type: | set of States |
Input labels coming out of state i
| Parameters: | i (int) – state |
|---|---|
| Returns: | set of input labels |
| Return type: | set of str |
New in version 1.0.
Rename a given state.
| Parameters: | |
|---|---|
| Returns: | self |
Note
Deals gacefully both with int and str names in the case of name collision.
Attention
the object is modified in place
Renames all states using a new list of names.
| Parameters: | nameList (list) – list of new names |
|---|---|
| Raises DFAerror: | |
| if provided list is too short | |
| Returns: | self |
Note
If no list of names is given, state indexes are used.
Attention
the object is modified in place
Returns a NFA that recognizes the reversal of the language
| Returns: | NFA recognizing reversal language |
|---|---|
| Return type: | NFA |
Tests if this two states have the same nullability
| Parameters: | |
|---|---|
| Return type: | bool |
Sets the final states of the FA
| Parameters: | statelist (int|list|set) – a list (or set) of final states indexes |
|---|
Caution
it erases any previous definition of the final state set.
Sets the initial state of a FA
| Parameters: | stateindex (int) – index of the initial state |
|---|
Defines the alphabet for the FA.
| Parameters: | symbolSet (list|set) – alphabet symbols |
|---|
Index of given state name.
| Parameters: | |
|---|---|
| Returns: | state index |
| Return type: | int |
| Raises DFAstateUnknown: | |
if the state name is unknown and autoCreate==False |
Note
Replaces stateName
Note
If the state name is not known and flag is set creates it on the fly
New in version 1.0.
Index of given state name.
| Parameters: | |
|---|---|
| Returns: | state index |
| Return type: | int |
| Raises DFAstateUnknown: | |
if the state name is unknown and autoCreate==False |
Deprecated since version 1.0: Use: stateIndex() instead
Bases: common.Drawable
Class of automata without initial or final states
| Variables: |
|
|---|
Bases: fa.FA
Base class for one-way automata .. inheritance-diagram:: OFA
Checks if FA is SP (Serial-PArallel), and if so returns the regular expression whose language is recognised by the FA
| Returns: | equivalent regular expression |
|---|---|
| Return type: | regexp |
| Raises NotSP: | if the automaton is not Serial-Parallel |
See also
Moreira & Reis, Fundamenta Informatica, Series-Parallel automata and short regular expressions, n.91 3-4, pag 611-629. http://www.dcc.fc.up.pt/~nam/publica/spa07.pdf
Note
Automata must be Serial-Parallel
Checks if the FA is acyclic
| Parameters: | strict (bool) – if not True loops are allowed |
|---|---|
| Returns: | True if the FA is acyclic |
| Return type: | bool |
Add transition :param int st1: departing state :param str sym: label :param int st2: arriving state
Evaluates the alphabetic length of the equivalent regular expression using every possible order of state elimination.
| Return type: | list of tuples (int, list of states) |
|---|
Transforms the automata into a complete one. If Sigma is empty nothing is done.
| Parameters: | dead (str) – dead state name |
|---|---|
| Returns: | the complete FA |
| Return type: | DFA |
Note
Adds a dead state (if necessary) so that any word can be processed with the automata. The new state is named dead, so this name should never be used for other purposes.
Attention
The object is modified in place.
Changed in version 1.0.
To be implemented below
| Parameters: | del_states (list) – states to be deleted |
|---|
Draw a transition in Dot Format
| Parameters: | |
|---|---|
| Return type: | str |
Returns a python representation of the object
| Returns: | the python representation (Tags,States,Sigma,delta,Initial,Final) |
|---|---|
| Return type: | tuple |
Eliminates every state that only have one successor and one predecessor.
| Returns: | GFA after eliminating states |
|---|---|
| Return type: | GFA |
Eliminate all transitions outgoing from a given state
| Parameters: | st (int) – the state index to loose all outgoing transitions |
|---|
Attention
performs in place alteration of the automata
New in version 0.9.6.
Tests if the automaton accepts a empty language
| Return type: | bool |
|---|
New in version 1.0.
Evaluates the number of cycles each state participates
| Returns: | state->list of cycle lengths |
|---|---|
| Return type: | dict |
Constructs the equivalent minimal DFA using Brzozowski’s algorithm
| Returns: | equivalent minimal DFA |
|---|---|
| Return type: | DFA |
Tests if the FA is minimal using Brzozowski’s algorithm
| Return type: | bool |
|---|
Regular expression from state elimination whose language is recognised by the FA. Uses a heuristic to choose the order of elimination.
| Returns: | the equivalent regular expression |
|---|---|
| Return type: | regexp |
Regular expression from state elimination whose language is recognised by the FA. Uses a heuristic to choose the order of elimination. The FA is not normalized before the state elimination.
| Returns: | the equivalent regular expression |
|---|---|
| Return type: | regexp |
State elimination Heuristic based on the number of cycles that passes through each state. Here those numbers are evaluated dynamically after each elimination step
| Returns: | an equivalent regular expression |
|---|---|
| Return type: | regexp |
See also
Nelma Moreira, Davide Nabais, and Rogério Reis. State elimination ordering strategies: Some experimental results. Proc. of 11th Workshop on Descriptional Complexity of Formal Systems (DCFS10), pages<PHONE_NUMBER>. DOI: 10.4204/EPTCS.31.16
State elimination Heuristic based on the number of cycles that passes through each state. Here those numbers are evaluated statically in the beginning of the process
| Returns: | a equivalent regular expression |
|---|---|
| Return type: | regexp |
See also
Nelma Moreira, Davide Nabais, and Rogério Reis. State elimination ordering strategies: Some experimental results. Proc. of 11th Workshop on Descriptional Complexity of Formal Systems (DCFS10), pages<PHONE_NUMBER>. DOI: 10.4204/EPTCS.31.16
Regular expression from state elimination whose language is recognised by the FA. The FA is normalized before the state elimination.
| Parameters: | order (list) – state elimination sequence |
|---|---|
| Returns: | the equivalent regular expression |
| Return type: | regexp |
Regular expression from state elimination whose language is recognised by the FA. The FA is not normalized before the state elimination.
| Parameters: | order (list) – state elimination sequence |
|---|---|
| Returns: | the equivalent regular expression |
| Return type: | regexp |
A regular expression obtained by state elimination algorithm whose language is recognised by the FA.
| Returns: | the equivalent regular expression |
|---|---|
| Return type: | regexp |
Topological order for the FA
| Returns: | List of state indexes |
|---|---|
| Return type: | list of int |
Note
self loops are taken in consideration
Bases: fa.OFA
Class for Deterministic Finite Automata.
Evaluates the action of a symbol over a state
| Parameters: |
|
|---|---|
| Returns: | the action of symbol over state |
| Return type: | int |
Computes almost equivalence, used by hyperMinimial
| Returns: | partition of states |
|---|---|
| Return type: | dictionary |
Note
may be optimized to avoid dupped
Adds a new transition from sti1 to sti2 consuming symbol sym.
| Parameters: | |
|---|---|
| Raises DFAnotNFA: | |
if one tries to add a non deterministic transition |
Completes a DFA assuming it is a minimal and avoiding de destruction of its minimality If the automaton is not complete, all the non final states are checked to see if tey are not already a dead state. Only in the negative case a new (dead) state is added to the automaton.
| Return type: | DFA |
|---|
Attention
The object is modified in place. If the alphabet is empty nothing is done
The Kernel of a ICDFA is the set of states that accept a non finite language.
| Returns: | triple (comp, center , mark) where comp are the strongly connected components, center the set of center states and mark the kernel states |
|---|---|
| Return type: | tuple |
Concatenation of two DFAs. If DFAs are not complete, they are completed.
| Parameters: |
|
|---|---|
| Returns: | the result of the concatenation |
| Return type: | DFA |
| Raises DFAdifferentSigma: | |
if alphabet are not equal |
Concatenation of two DFAs.
| Parameters: |
|
|---|---|
| Returns: | the result of the concatenation |
| Return type: | DFA |
| Raises DFAdifferentSigma: | |
if alphabet are not equal |
New in version 0.9.5.
Note
this is to be used with non complete DFAs
Remove a transition if existing and perform cleanup on the transition function’s internal data structure.
| Parameters: |
|---|
Note
Unused alphabet symbols will be discarded from Sigma.
Delete given iterable collection of states from the automaton.
| Parameters: | del_states – collection of int representing states |
|---|
Note
delta function will always be rebuilt, regardless of whether the states list to remove is a suffix, or a sublist, of the automaton’s states list.
Evaluate the distinguishability language for a DFA
| Return type: | DFA |
|---|
See also
Cezar Câmpeanu, Nelma Moreira, Rogério Reis: The distinguishability operation on regular languages. NCMA 2014: 85-100
New in version 0.9.8.
Evaluates the list of minimal words that distinguish each pair of states
| Returns: | set of minimal distinguishing words |
|---|---|
| Return type: | FL |
New in version 0.9.8.
Attention
If the DFA is not minimal, the method loops forever
Evaluate the right distinguishability language for a DFA
| Return type: | DFA |
|---|
Compute distRMin for DFA
:rtype FL
Evaluate the two-sided distinguishability language for a DFA
| Return type: | DFA |
|---|
returns the set of words of words of length up to n accepted by self :param n: highest length or all words if finite :type n: int
| Return type: | list of strings or None |
|---|
Verify if the two automata are equivalent. Both are verified to be minimum and complete, and then one is matched against the other... Doesn’t destroy either dfa...
| Parameters: | other (DFA) – the other DFA |
|---|---|
| Return type: | bool |
Returns the state reached from given state through a given symbol.
| Parameters: |
|
|---|---|
| Returns: | reached state |
| Return type: | int |
| Raises: |
|
Returns the state reached from a given state.
| Parameters: | |
|---|---|
| Returns: | reached state or -1 |
| Return type: | set of int |
| Raises DFAsymbolUnknown: | |
if symbol not in alphabet |
New in version 0.9.5.
Note
this is to be used with non complete DFAs
Returns the set of states reached from a given set of states through a given symbol
| Parameters: |
|
|---|---|
| Returns: | set of reached states |
| Return type: | set of int |
Returns the set of states reached from a given set of states through a given symbol
| Parameters: |
|
|---|---|
| Returns: | set of reached states |
| Return type: | set of int |
New in version 0.9.5.
Note
this is to be used with non complete DFAs
Verifies if the DFA recognises a given word
| Parameters: |
|
|---|---|
| Return type: | bool |
Verifies if there is a final state in strongly connected component containing s.
| Parameters: | s (int) – state |
|---|---|
| Returns: | 1 if yes, 0 if no |
Tests if the automaton has a dead trap state
| Return type: | bool |
|---|
New in version 1.1.
Hyperminization of a minimal DFA
| Parameters: | strict (bool) – if strict=True it first minimizes the DFA |
|---|---|
| Returns: | an hyperminimal DFA |
| Return type: | DFA |
See also
M. Holzer and A. Maletti, An nlogn Algorithm for Hyper-Minimizing a (Minimized) Deterministic Automata, TCS 411(38-39): 3404-3413 (2010)
Note
if strict=False minimality is assumed
Returns the in-degree of a given state in an FA
| Parameters: | st (int) – index of the state |
|---|---|
| Return type: | int |
Evaluates the connected component starting at the initial state.
| Returns: | list of state indexes in the component |
|---|---|
| Return type: | list of int |
Tests if a state is initial
| Parameters: | state (int) – state index |
|---|---|
| Return type: | bool |
The set of initial states
| Returns: | the set of the initial states |
|---|---|
| Return type: | set of States |
Merge a list of states.
| Parameters: | lst (iterable of state indexes.) – set of equivalent states |
|---|
Mark states with indexes s1 and s2 in given map as non equivalent states. If any back-effects exist, apply them.
| Parameters: |
|---|
Merge the first given state into the second. If the first state is an initial state the second becomes the initial state.
| Parameters: |
|---|
Attention
It is up to the caller to remove the disconnected state. This can be achieved with `trim().
Evaluates the equivalent minimal complete DFA
| Parameters: |
|
|---|---|
| Returns: | equivalent minimal DFA |
| Return type: | DFA |
Tests the DFA’s minimality using Hopcroft and Karp’s state equivalence algorithm
| Returns: | bool |
|---|
See also
J. E. Hopcroft and R. M. Karp.A Linear Algorithm for Testing Equivalence of Finite Automata.TR 71–114. U. California. 1971
Attention
The automaton must be complete.
Evaluates the equivalent minimal complete DFA using Hopcroft algorithm
| Returns: | equivalent minimal DFA |
|---|---|
| Return type: | DFA |
See also
John Hopcroft,An nlog{n} algorithm for minimizing states in a finite automaton.The Theory of Machines and Computations.AP. 1971
Minimizes the DFA with an incremental method using the Union-Find algorithm and memoized non-equivalence intermediate results
| Parameters: | minimal_test (bool) – starts by verifying that the automaton is not minimal? |
|---|---|
| Returns: | equivalent minimal DFA |
| Return type: | DFA |
See also
Evaluates the equivalent minimal automata with Moore’s algorithm
See also
John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, AW, 1979
| Returns: | minimal complete DFA |
|---|---|
| Return type: | DFA |
Evaluates the equivalent minimal complete DFA using Moore’s (quadratic) algorithm
See also
John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, AW, 1979
| Returns: | equivalent minimal DFA |
|---|---|
| Return type: | DFA |
Tests if a DFA is minimal using the quadratic version of Moore’s algorithm
| Return type: | bool |
|---|
Tests if a non necessarely complete DFA is minimal, i.e., if the DFA is non complete, if the minimal complete has only one more state.
| Returns: | True if not minimal |
|---|---|
| Return type: | bool |
Attention
obsolete: use minimalP
Tests if the DFA is minimal by computing the set of distinguishable (not equivalent) pairs of states
| Return type: | bool |
|---|
Tests if the DFA is minimal
| Parameters: | method – the minimization algorithm to be used |
|---|---|
| Return type: | bool |
..note: if DFA non complete test if complete minimal has one more state
Evaluates the equivalent minimal complete DFA using Waton’s incremental algorithm
| Parameters: | test_only (bool) – is it only to test minimality |
|---|---|
| Returns: | equivalent minimal DFA |
| Return type: | DFA |
| Raises DFAnotComplete: | |
| if automaton is not complete |
Tests if a DFA is minimal using Watson’s incremental algorithm
| Return type: | bool |
|---|
Test non equivalence of two DFAs
| Parameters: | other (DFA) – the other DFA |
|---|---|
| Return type: | bool |
Returns pair graph
| Return type: | DiGraphVM |
|---|
See also
A graph theoretic approach to automata minimality. Antonio Restivo and Roberto Vaglica. Theoretical Computer Science, 429 (2012) 282-291. doi:10.1016/j.tcs.2011.12.049 Theoretical Computer Science, 2012 vol. 429 (C) pp. 282-291. http://dx.doi.org/10.1016/j.tcs.2011.12.049
Prints table of compatibility (in the context of the minimalization algorithm).
| Parameters: | data – data to print |
|---|
Returns a DFA resulting of the simultaneous execution of two DFA. No final states set.
| Parameters: |
|
|---|---|
| Return type: | DFA |
Returns a regexp for the current DFA considering the recursive method. Very inefficent.
| Returns: | a regexp equivalent to the current DFA |
|---|---|
| Return type: | regexp |
Reorders states according to given dictionary. Given a dictionary (not necessarily complete)... reorders states accordingly.
:param dicti :type dicti: dictionary
Evaluate reverse transition function.
| Parameters: | rev (DFA) – DFA in which the reverse function will be stored |
|---|
Evaluation of the syntactic monoid of a DFA
| Returns: | the semigroup |
|---|---|
| Return type: | SSemiGroup |
Evaluation of the syntactic semigroup of a DFA
| Returns: | the semigroup |
|---|---|
| Return type: | SSemiGroup |
Shuffle of two languages: L1 W L2
| Parameters: |
|
|---|---|
| Return type: | DFA |
See also
C. Câmpeanu, K. Salomaa and S. Yu, Tight lower bound for the state complexity of shuffle of regular languages. J. Autom. Lang. Comb. 7 (2002) 303–310.
Strange operation
| Parameters: | other (DFA) – the other automaton |
|---|---|
| Return type: | DFA |
New in version 1.2b2.
Star of a DFA. If the DFA is not complete, it is completed.
..versionchanged: 0.9.6
| Parameters: | flag (bool) – plus instead of star |
|---|---|
| Returns: | the result of the star |
| Return type: | DFA |
Set of children of a state
| Parameters: | |
|---|---|
| Returns: | map children -> multiplicity |
| Return type: | dictionary |
Returns a dfa that recognizes subword(L(self))
| Return type: | dfa |
|---|
New in version 1.1.
Collects the transition information in a compact way suitable for graphical representation. :rtype: list of tupples
New in version 0.9.8.
Evaluates the power automata for the action of each symbol
| Returns: | The power automata being the set of all states the initial state and all singleton states final. |
|---|---|
| Return type: | DFA |
Evaluates the regular expression corresponding to the synchronizing pwords of the automata.
| Returns: | a regular expression of the sync words of the automata |
|---|---|
| Return type: | regexp |
Try to convert DFA to ADFA
| Returns: | the same automaton as a ADFA |
|---|---|
| Return type: | ADFA |
| Raises notAcyclic: | |
| if this is not an acyclic DFA |
New in version 1.2.
Normalise unique string for the string icdfa’s representation.
See also
TCS 387(2):93-102, 2007 http://www.ncc.up.pt/~nam/publica/tcsamr06.pdf
| Returns: | normalised representation |
|---|---|
| Return type: | list |
| Raises DFAnotComplete: | |
| if DFA is not complete |
Unmarked NFA that corresponds to a marked DFA: in which each alfabetic symbol is a tuple (symbol, index)
| Returns: | a NFA |
|---|---|
| Return type: | NFA |
Set of states reacheable from the given initial state(s) that have a path to a final state.
| Parameters: | initial_states (iterable of int) – starting states |
|---|---|
| Returns: | set of state indexes |
| Return type: | set of int |
Generation of Verso interface description
New in version 0.9.5.
| Returns: | the interface list |
|---|
Returns a witness for the difference of two DFAs and:
| 0 | if the witness belongs to the other language |
| 1 | if the witness belongs to the self language |
| Parameters: | other (DFA) – the other DFA |
|---|---|
| Returns: | a witness word |
| Return type: | list of symbols |
| Raises DFAequivalent: | |
| if automata are equivalent |
Bases: fa.OFA
Class for Non-deterministic Finite Automata (epsilon-transitions allowed).
Add epsilon loops to every state :return: self
Attention
in-place modification
New in version 1.0.
Add a new state to the set of initial states.
| Parameters: | stateindex (int) – index of new initial state |
|---|
Adds a new transition. Transition is from sti1 to sti2 consuming symbol sym. sti2 is a unique state, not a set of them.
| Parameters: |
|---|
Add transition to the new transducer instance.
| Parameters: |
|---|
New in version 1.0.
Largest right invariant equivalence between states of the NFA
| Returns: | Incomplete equivalence relation (transitivity, and reflexivity not calculated) as a set of unordered pairs of states |
|---|---|
| Return type: | Set of frozensets |
See also
Ilie&Yu, 2003
Alternative space-efficient definition of NFA.autobisimulation.
| Returns: | Incomplete equivalence relation (reflexivity, symmetry, and transitivity not calculated) as a set of pairs of states |
|---|---|
| Return type: | list of tuples |
Add all non epsilon transitions from the states in the epsilon closure of given state to given state.
| Parameters: | st (int) – state index |
|---|
Concatenation of NFA
| Parameters: |
|
|---|---|
| Returns: | the result of the concatenation |
| Return type: | NFA |
Remove a transition if existing and perform cleanup on the transition function’s internal data structure.
| Parameters: |
|---|
Note
unused alphabet symbols will be discarded from Sigma.
Delete given iterable collection of states from the automaton.
| Parameters: | del_states (set|list) – collection of int representing states |
|---|
Note
delta function will always be rebuilt, regardless of whether the states list to remove is a suffix, or a sublist, of the automaton’s states list.
A dot representation :arg direction: direction of drawing :arg size: size of image :arg sep: line separator :return: the dot representation type sep: str :type direction: str :type size: str :rtype: str
New in version 0.9.6.
Changed in version 0.9.8.
Eliminate epsilon-transitions from this automaton.
:rtype : NFA
Attention
performs in place modification of automaton
Changed in version 1.1.1.
Eliminates all epslilon-transitions with no state addition
Attention
in-place modification
Delete all trasitions through a given symbol
| Parameters: | symbol (str) – the symbol to be excluded from delta |
|---|
Attention
in place alteration of the automata
New in version 0.9.6.
returns the set of words of words of length up to n accepted by self :param n: highest lenght or all words if finite :type n: int
| Return type: | list of strings or None |
|---|
Returns the set of states epsilon-connected to from given state or set of states.
| Parameters: | st (int|set) – state index or set of state indexes |
|---|---|
| Returns: | the list of state indexes epsilon connected to st |
| Return type: | set of int |
Attention
st must exist.
All states in all paths (DFS) through empty words from a given starting state to a given ending state.
| Parameters: | |
|---|---|
| Returns: | states in epsilon paths from start to end |
| Return type: | set of states |
Equivalent NFA reduced according to given equivalence classes.
| Parameters: | equiv_classes (UnionFind) – Equivalence classes |
|---|---|
| Returns: | Equivalent NFA |
| Return type: | NFA |
Set of states reacheable from given states through given symbol and epsilon closure.
| Parameters: |
|
|---|---|
| Returns: | set of reached state indexes |
| Return type: | set[int] |
| Raises DFAsymbolUnknown: | |
if symbol is not in alphabet |
Verify if the NFA recognises given word.
| Parameters: | word (str) – word to be recognised |
|---|---|
| Return type: | bool |
Verify whether there is a final state in strongly connected component containing given state.
| Parameters: | s (int) – state index |
|---|---|
| Returns: | :: bool |
Whether there’s a transition from given state, optionally through given symbol, and optionally to a specific target.
| Parameters: | |
|---|---|
| Returns: | if there is a transition |
| Return type: | bool |
Whether this NFA is homogenous; that is, for all states, whether all incoming transitions to that state are through the same symbol.
| Parameters: | x – dummy parameter to agree with the method in DFAr |
|---|---|
| Return type: | bool |
Evaluate the connected component starting at the initial state.
| Returns: | list of state indexes in the component |
|---|---|
| Return type: | list of int |
Equivalent NFA obtained from merging equivalent states from autobisimulation of this NFA’s reversal.
| Return type: | NFA |
|---|
Note
returns copy of self if autobisimulation renders no equivalent states.
Equivalent NFA obtained from merging equivalent states from autobisimulation of this NFA, and from autobisimulation of its reversal; i.e., merges all states that are equivalent w.r.t. the largest right invariant and largest left invariant equivalence relations.
| Return type: | NFA |
|---|
Note
returns copy of self if autobisimulations render no equivalent states.
Evaluates the equivalent minimal DFA
| Returns: | equivalent minimal DFA |
|---|---|
| Return type: | DFA |
Evaluates the equivalent minimal complete DFA
| Returns: | equivalent minimal DFA |
|---|---|
| Return type: | DFA |
Returns a NFA (skeletom) resulting of the simultaneous execution of two DFA.
| Parameters: | other (NFA) – the other automata |
|---|---|
| Return type: | NFA |
Note
No final states are set.
Attention
Equivalent NFA obtained from merging equivalent states from autobisimulation of this NFA.
| Return type: | NFA |
|---|
Note
returns copy of self if autobisimulation renders no equivalent states.
Reorder states indexes according to given dictionary.
| Parameters: | dicti (dictionary) – state name reorder |
|---|
Note
dictionary does not have to be complete
Returns a NFA that recognizes the reversal of the language
| Returns: | NFA recognizing reversal language |
|---|---|
| Return type: | NFA |
Evaluate reverse transition function.
| Parameters: | rev (NFA) – NFA in which the reverse function will be stored |
|---|
Sets the initial states of an NFA
| Parameters: | statelist (set|list|int) – an iterable of initial state indexes |
|---|
Shuffle of a NFA
| Parameters: | other (FA) – an FA |
|---|---|
| Returns: | the resulting NFA |
| Return type: | NFA |
Kleene star of a NFA
| Parameters: | flag (Boolean) – plus instead of star |
|---|---|
| Returns: | the resulting NFA |
| Return type: | NFA |
Set of children of a state
| Parameters: | |
|---|---|
| Returns: | children states |
| Return type: | Set of int |
Collects the transition information in a concat way suitable for graphical representation. :rtype: list
Construct a DFA equivalent to this NFA, by the subset construction method.
| Return type: | DFA |
|---|
Note
valid to epsilon-NFA
NFA with the reverse mapping of the delta function.
| Returns: | shallow copy with reverse delta function added |
|---|---|
| Return type: | NFAr |
Set of states reacheable from the given initial state(s) that have a path to a final state.
| Parameters: | initial_states (set of int or list of int) – set of initial states |
|---|---|
| Returns: | set of state indexes |
| Return type: | set of int |
Bases: fa.NFA
Class for Non-deterministic Finite Automata with reverse delta function added by construction.
| Variables: | deltaReverse – the reversed transition function |
|---|
Note
Includes efficient methods for merging states.
Adds a new transition. Transition is from sti1 to sti2 consuming symbol sym. sti2 is a unique state, not a set of them. Reversed transition function is also computed
| Parameters: |
|---|
Remove a transition if existing and perform cleanup on the transition function’s internal data structure and in the reversal transition function
| Parameters: |
|---|
Delete given iterable collection of states from the automaton. Performe deletion in the transition function and its reversal.
| Parameters: | del_states (set or list of int) – collection of int representing states |
|---|
Eliminate epsilon-transitions from this automaton, with reduction of states through elimination of epsilon-cycles, and single epsilon-transition cases.
| Returns: | itself |
|---|---|
| Return type: |
Attention
performs inplace modification of automaton
Checks is the automaton is homogenous, i.e.the transitions that reaches a state have all the same label.
| Parameters: | inplace (bool) – if True performs epsilon transitions elimination |
|---|---|
| Returns: | True if homogenous |
| Return type: | bool |
Merge the first given state into the second. If first state is an initial or final state, the second becomes respectively an initial or final state.
| Parameters: |
|---|
Attention
It is up to the caller to remove the disconnected state. This can be achieved with `trim().
Merge a set of states with a target merge state. If the states in the set have transitions among them, those transitions will be directly merged into the target state.
| Parameters: |
|
|---|
Note
if target state is not given, the minimal index with be considered.
Attention
The states of the list will become unreacheable, but won’t be removed. It is up to the caller to remove them. That can be achieved with trim().
Turn into an instance of NFA, and remove the reverse mapping of the delta function.
| Returns: | shallow copy without reverse delta function |
|---|---|
| Return type: | NFA |
If given state has only one incoming transition (indegree is one), and it’s through epsilon, then remove such transition and return the source state.
| Parameters: | state (int) – state to check |
|---|---|
| Returns: | source state |
| Return type: | int or None |
Note
if conditions aren’t met, returned source state is None, and automaton remains unmodified.
If given state has only one outgoing transition (outdegree is one), and it’s through epsilon, then remove such transition and return the target state.
| Parameters: | state (int) – state to check |
|---|---|
| Returns: | target state |
| Return type: | int or None |
Note
if conditions aren’t met, returned target state is None, and automaton remains unmodified.
Bases: fa.OFA
Class for Generalized Finite Automata: NFA with a unique initial state and transitions are labeled with regexp.
| Parameters: | |
|---|---|
| Raises DFAepsilonRedefenition: | |
if sym is Epsilon |
Adds empty set transitions between the automatons final and initial states in order to make it complete. It’s only meant to be used in the final stage of SEA...
Deletes a state and updates the automaton
| Parameters: | st (state index) – the state to be deleted |
|---|
Create a single initial and final state with Epsilon transitions.
Attention
works in place
Reorder states indexes according to given dictionary.
| Parameters: | dictio (dictionary) – order |
|---|
Note
dictionary does not have to be complete
Set of children of a state
| Parameters: | |
|---|---|
| Returns: | map: children -> alphabetic length |
| Return type: | dictionary |
Bases: object
Class support for the Syntactic SemiGroup.
| Variables: |
|
|---|
Representative of an element given as index
| Parameters: | i (int) – index of the element |
|---|---|
| Returns: | the first word originating the element |
| Return type: | str |
Representative of an element given as prefix symb
| Parameters: | |
|---|---|
| Returns: | word |
| Return type: | str |
Bases: object
Class for enumerate FA languages
| Variables: |
|
|---|
New in version 0.9.8.
See also
Efficient enumeration of words in regular languages, M. Ackerman and J. Shallit, Theor. Comput. Sci. 410, 37, pp 3461-3470. 2009. http://dx.doi.org/10.1016/j.tcs.2009.03.018
Enumerates the first m words of L(A) according to the lexicographic order if there are at least m words. Otherwise, enumerates all words accepted by A.
| Parameters: | m (int) – |
|---|
Enumerates the nth cross-section of L(A)
| Parameters: | n (int) – nonnegative integer |
|---|
Finite automata definition as a string using the input format.
New in version 0.9.5.
Changed in version 0.9.6: Names are now used instead of indexes.
Changed in version 0.9.7: New format with quotes and alphabet
| Parameters: |
|
|---|---|
| Returns: | the representation |
| Return type: | str |
Common definitions for FAdo files
In/Out.
FAdo IO.
Reads list of finite automata definition from a file.
| Parameters: | FileName (str) – file name |
|---|---|
| Return type: | list |
The format of these files must be the as simple as possible:
|
FAdo ::= FA | FA CR FAdo FA ::= DFA | NFA | Transducer DFA ::= "@DFA" LsStates Alphabet CR dTrans NFA ::= "@NFA" LsStates Initials Alphabet CR nTrans Transducer ::= "@Transducer" LsStates Initials Alphabet Output CR tTrans Initials ::= "*" LsStates | \epsilon Alphabet ::= "$" LsSymbols | \epsilon Output ::= "$" LsSymbols | \epsilon nSymbol ::= symbol | "@epsilon" LsStates ::= stateid | stateid , LsStates LsSymbols ::= symbol | symbol , LsSymbols dTrans ::= stateid symbol stateid | | stateid symbol stateid CR dTrans nTrans ::= stateid nSymbol stateid | | stateid nSymbol stateid CR nTrans tTrans ::= stateid nSymbol nSymbol stateid | | stateid nSymbol nSymbol stateid CR nTrans
Note
If an error occur, either syntactic or because of a violation of the declared automata type, an exception is raised
Changed in version 0.9.6.
Changed in version 1.0.
Regular expressions manipulation
Regular expression classes and manipulation
Bases: object
Base class for regular expressions.
Used directly to represent a symbol. The type of the symbol is arbitrary.
| Variables: |
|
|---|
Constructor of a regular expression symbol.
| Parameters: | val – the actual symbol |
|---|
Closure of partial derivatives of the regular expression in relation to all words.
| Returns: | set of regular expressions |
|---|---|
| Return type: | set |
See also
Antimirov, 95
Number of occurrences of alphabet symbols in the regular expression.
| Return type: | integer |
|---|
Attention
Doesn’t include the empty word.
Compare with another regular expression for equivalence. :param r: :param cmp_method: :param nfa_method:
Compare with another regular expression for equivalence through minimal DFAs. :param r: :param nfa_method:
Derivative of the regular expression in relation to the given symbol.
| Parameters: | sigma – an arbitrary symbol. |
|---|---|
| Return type: | regular expression |
Note
whether the symbols belong to the expression’s alphabet goes unchecked. The given symbol will be matched against the string representation of the regular expression’s symbol.
See also
Deterministic position automaton of a regular expression.
| Returns: | position DFA |
|---|---|
| Return type: | DFA |
| Raises common.DFAnotNFAFAdo: | |
| if not DFA |
Note
If this expression is not linear (cf. linearP()), exception may be raised on non-deterministic transitions.
Number of occurrences of the empty word in the regular expression.
| Return type: | integer |
|---|
Verifies if a word is a member of the language represented by the regular expression.
| Parameters: | word (str) – the word |
|---|---|
| Return type: | bool |
Whether the empty word property holds for this regular expression’s language.
| Return type: | Boolean |
|---|
List of possible symbols matching the first symbol of a string in the language of the regular expression.
| Parameters: | parent_first – |
|---|---|
| Returns: | list of symbols |
Map of each symbol’s follow list in the regular expression.
| Parameters: | lists – |
|---|---|
| Returns: | map of symbols’ follow lists |
| Return type: | {symbol: list of symbols} |
Attention
For first() and last() return lists, the follow list for certain symbols might have repetitions in the case of follow maps calculated from star operators. The union of last(), first() and follow() sets are always disjoint when the regular expression is in star normal form ( Brüggemann-Klein, 92), therefore FAdo implements them as lists. You should order exclusively, or take a set from a list in order to resolve repetitions.
Map of each symbol’s follow list in the regular expression.
| Parameters: | lists – |
|---|---|
| Returns: | map of symbols’ follow lists |
| Return type: | {symbol: list of symbols} |
Attention
For first() and last() return lists, the follow list for certain symbols might have repetitions in the case of follow maps calculated from star operators. The union of last(), first() and follow() sets are always disjoint
See also
Sabine Broda, António Machiavelo, Nelma Moreira, and Rogério Reis. On the average size of glushkov and partial derivative automata. International Journal of Foundations of Computer Science, 23(5):969-984, 2012.
Map of each symbol’s follow list in the regular expression under a star.
| Parameters: | lists – |
|---|---|
| Returns: | map of symbols’ follow lists |
| Return type: | {symbol: list of symbols} |
List of possible symbols matching the last symbol of a string in the language of the regular expression.
| Parameters: | parent_last – |
|---|---|
| Returns: | list of symbols |
| Return type: | list |
Linear form of the regular expression , as a mapping from heads to sets of tails, so that each pair (head, tail) is a monomial in the set of linear forms.
| Returns: | dictionary mapping heads to sets of tails |
|---|---|
| Return type: | {symbol: set([regular expressions])} |
See also
Antimirov, 95
Whether the regular expression is linear; i.e., the occurrence of a symbol in the expression is unique.
| Return type: | boolean |
|---|
Regular expression in which every alphabetic symbol is marked with its position.
The kind of regular expression returned is known, depending on the literary source, as marked, linear or restricted regular expression.
| Returns: | linear regular expression |
|---|---|
| Return type: | regexp |
See also
R. McNaughton and H. Yamada, Regular Expressions and State Graphs for Automata, IEEE Transactions on Electronic Computers, V.9 pp:39-47, 1960
..attention: mark and unmark do not preserve the alphabet, neither set the new alphabet
A list with four measures for regular expressions.
| Parameters: | from_parent – |
|---|---|
| Return type: | [int,int,int,int] |
[alphabeticLength, treeLength, epsilonLength, starHeight]
Attention
Methods for each of the measures are implemented independently. This is the most effective for obtaining more than one measure.
NFA that accepts the regular expression’s language, whose structure, and construction.
| Return type: | NFA |
|---|
See also
Ilie & Yu (Follow Automata, 03)
Epsilon-NFA constructed with Ilie and Yu’s method () that accepts the regular expression’s language.
| Parameters: | trim – |
|---|---|
| Returns: | NFA possibly with epsilon transitions |
| Return type: | NFAe |
See also
Ilie & Yu, Follow automta, Inf. Comp. ,v. 186 (1),140-162,2003
Position or Glushkov automaton of the regular expression. Recursive method.
| Returns: | NFA |
|---|
NFA that accepts the regular expression’s language, and is equal in structure to the follow automaton.
| Return type: | NFA |
|---|
Note
Included for testing purposes.
See also
Ilie & Yu (Follow Automata, 2003)
| Returns: | partial derivatives [or equation] automaton |
|---|---|
| Return type: | NFA |
See also
V. M. Antimirov, Partial Derivatives of Regular Expressions and Finite Automaton Constructions .Theor. Comput. Sci.155(2): 291-319 (1996)
Note
optimized version
| Returns: | partial derivatives [or equation] automaton |
|---|---|
| Return type: | NFA |
Position or Glushkov automaton of the regular expression constructed from the expression’s star normal form.
| Returns: | position automaton |
|---|---|
| Return type: | NFA |
Position automaton of the regular expression.
| Parameters: | lstar (boolean) – if not None followlists are computed dijunct |
|---|---|
| Returns: | position NFA |
| Return type: | NFA |
Epsilon-NFA constructed with Thompson’s method that accepts the regular expression’s language.
| Return type: | NFA |
|---|
See also
Set of partial derivatives of the regular expression in relation to given symbol.
| Parameters: | sigma – symbol in relation to which the derivative will be calculated. |
|---|---|
| Returns: | set of regular expressions |
See also
Antimirov, 95
Equivalent regular expression with the following cases simplified:
| Parameters: | hasEpsilon – used internally to indicate that the language of which this term is a subterm has the empty word. |
|---|---|
| Returns: | regular expression |
Attention
Returned structure isn’t strictly a duplicate. Use __copy__() for that purpose.
Set of symbols that occur in a regular expression..
| Returns: | set of symbols |
|---|---|
| Return type: | set of symbols |
Set the alphabet for a regular expression and all its nodes
| Parameters: |
|
|---|
..attention: Normally this attribute is not defined in a regexp()
Star Normal Form (SNF) of the regular expression.
| Parameters: | hollowdot – |
|---|---|
| Returns: | regular expression in star normal form |
Maximum level of nested regular expressions with a star operation applied.
For instance, starHeight(((a*b)*+b*)*) is 3.
| Return type: | integer |
|---|
Length of the string representation of the regular expression.
| Return type: | integer |
|---|
‘Support of a regular expression.
| Returns: | set of regular expressions |
|---|---|
| Return type: | set |
See also
Champarnaud, J.M., Ziadi, D.: From Mirkin’s prebases to Antimirov’s word partial derivative. Fundam. Inform. 45(3), 195-205 (2001)
NFA that accepts the regular expression’s language. :param nfa_method:
Number of nodes of the regular expression’s syntactical tree.
| Return type: | integer |
|---|
The unmarked form of the regular expression. Each leaf in its syntactical tree becomes a regexp(), the epsilon() or the emptyset().
| Return type: | (general) regular expression |
|---|
| Parameters: | word – list of arbitrary symbols. |
|---|---|
| Return type: | regular expression |
See also
Bases: reex.regexp
Base class for Epsilon and EmptySet
| Parameters: | sigma – |
|---|
Bases: reex.specialConstant
Class that represents the empty word.
| Parameters: | sigma – |
|---|
Bases: reex.specialConstant
Class that represents the empty set.
| Parameters: | sigma – |
|---|
Bases: reex.regexp
Base class for concatenation, and disjunction operations.
Bases: reex.connective
Class for catenation operation on regular expressions.
Bases: reex.regexp
Class for marked regular expression symbols.
Reads a regexp from string.
| Parameters: |
|
|---|---|
| Return type: | regexp |
Extended regular expressions manipulation
Extended regular expression classes and its manipulation
New in version 0.9.8.
Bases: reex.regexp
Base class for extended regular expressions, used directly to represent a symbol.
| Variables: | val – the actual symbol |
|---|
Constructor of a regular expression symbol.
| Parameters: | val – the actual symbol |
|---|
Closure of partial derivatives of the regular expression in relation to all words.
| Returns: | set of regular expressions |
|---|---|
| Return type: | set |
Compare with another regular expression for equivalence. :param r: :param cmp_method: :param nfa_method:
Computes the concatenation of two regular expressions.
| Parameters: | r (xre) – a regular expression |
|---|---|
| Return type: | xre |
Derivative of the regular expression in relation to the given symbol.
| Parameters: | sigma – an arbitrary symbol. |
|---|---|
| Return type: | regular expression |
Note
whether the symbols belong to the expression’s alphabet goes unchecked. The given symbol will be matched against the string representation of the regular expression’s symbol.
See also
Word derivatives automaton of the regular expression
| Returns: | word derivatives automaton |
|---|---|
| Return type: | DFA |
See also
Verifies if two regular expressions are equivalent.
| Parameters: | reg – regular expression |
|---|---|
| Return type: | bool |
Computes the intersection of two regular expressions.
| Parameters: | sx (xre) – a regular expression |
|---|---|
| Return type: | xre |
| Returns: | dictionary mapping heads to sets of tails |
|---|---|
| Return type: | {symbol: set([regular expressions])} |
See also
Antimirov, 95
| Returns: | partial derivatives [or equation] automaton |
|---|---|
| Return type: | NFA |
See also
V. M. Antimirov, Partial Derivatives of Regular Expressions and Finite Automaton Constructions. Theor. Comput. Sci.155(2): 291-319 (1996)
..attention why different from reex.nfaPD
‘Support of a regular expression.
| Returns: | set of regular expressions |
|---|---|
| Return type: | set |
See also
Champarnaud, J.M., Ziadi, D.: From Mirkin’s prebases to Antimirov’s word partial derivative. Fundam. Inform. 45(3), 195-205 (2001)
DFA that accepts the regular expression’s language. :param dfa_method:
Finite Tranducer Support
Transducer manipulation.
New in version 1.0.
Bases: transducers.GFT
Standard Form Tranducer
| Variables: | Output (set) – output alphabet |
|---|
Add a loop transition with epsilon input and output to every state in the transducer.
Add a new symbol to the output alphabet
There is no problem with duplicate symbols because Output is a Set. No symbol Epsilon can be added
| Parameters: | sym (str) – symbol or regular expression to be added |
|---|
Add transition to the new transducer instance.
| Parameters: |
|---|
Composition operation of a transducer with a transducer.
| Parameters: | other (SFT) – the second transducer |
|---|---|
| Return type: | SFT |
Concatenation of transducers
| Parameters: | other (SFT) – the other operand |
|---|---|
| Return type: | SFT |
Remove a transition if existing and perform cleanup on the transition function’s internal data structure.
| Parameters: |
|---|
Remove given state and transitions related with that state.
| Parameters: | sti (int) – index of the state to be removed |
|---|---|
| Raises DFAstateUnknown: | |
| if state index does not exist |
Delete given iterable collection of states from the automaton.
| Parameters: | lstates (set|list) – collection of int representing states |
|---|
Duplicate of itself :rtype: SFT
Attention
only duplicates the initially connected component
Tests whether the transducer returns the second word using the first one as input
| Parameters: | wp (tuple) – pair of words |
|---|---|
| Return type: | bool |
Tests if a transducer is functional using Allauzer & Mohri and Béal&Carton&Prieur&Sakarovitch algorithms.
| Return type: | bool |
|---|
See also
Cyril Allauzer and Mehryar Mohri, Journal of Automata Languages and Combinatorics, Efficient Algorithms for Testing the Twins Property, 8(2): 117-144, 2003.
See also
M.P. Béal, O. Carton, C. Prieur and J. Sakarovitch. Squaring transducers: An efficient procedure for deciding functionality and sequentiality. Theoret. Computer Science 292:1 (2003), 45-63.
Note
This is implemented using nonFunctionalW()
Conjunction of transducer and automata: X & Y.
| Parameters: | other (DFA|NFA) – the automata needs to be operated. |
|---|---|
| Return type: | SFT |
Switch the input label with the output label.
No initial or final state changed.
| Returns: | Transducer with transitions switched. |
|---|---|
| Return type: | SFT |
Returns a witness of non funcionality (if is that the case) or a None filled triple
| Returns: | witness |
|---|---|
| Return type: | tuple |
Conjunction of transducer and automaton: X & Y using output intersect operation.
| Parameters: | other (DFA|NFA) – the automaton used as a filter of the output |
|---|---|
| Return type: | SFT |
Naive version of outIntersection
| Parameters: | other (DFA|NFA) – the automaton used as a filter of the output |
|---|---|
| Return type: | SFT |
Output label coming out of the state i
| Parameters: | s (int) – index state |
|---|---|
| Return type: | set |
Returns a transducer (skeleton) resulting from the execution of the transducer with the automaton as filter on the input.
| Parameters: | other (NFA) – the automaton used as filter |
|---|---|
| Return type: | SFT |
Returns a transducer that recognizes the reversal of the relation.
| Returns: | Transducer recognizing reversal language |
|---|---|
| Return type: | SFT |
Result of applying a transducer to an automaton
| Parameters: | nfa (DFA|NFA) – input language to transducer |
|---|---|
| Returns: | resulting language |
| Return type: | NFA |
Returns the automaton accepting the outup of the transducer on the input word
| Parameters: | word – the word |
|---|---|
| Return type: | NFA |
Sets the initial state of a Transducer
| Parameters: | sts (list) – list of states |
|---|
Kleene star
| Parameters: | flag (bool) – plus instead of star |
|---|---|
| Returns: | the resulting Transducer |
| Return type: | SFT |
Delete the output labels in the transducer. Translate it into an NFA
| Return type: | NFA |
|---|
Returns the result of considering the output symbols of the transducer as input symbols of a NFA (ignoring the input symbol, thus)
| Returns: | the NFA |
|---|---|
| Return type: | NFA |
Finite languages and related automata manipulation
Finite languages manipulation
Bases: object
Finite Language Class
| Variables: |
|
|---|
Difference of FL: a - b
| Parameters: | other (FL) – right hand operand |
|---|---|
| Return type: | FL |
| Raises FAdoGeneralError: | |
| if both arguments are not FL |
Separates a language in two other using a DFA of NFA as a filter
| Parameters: | automata (DFA|NFA) – the automata to be used as a filter |
|---|---|
| Returns: | the accepted/unaccepted pair of languages |
| Return type: | tuple of FL |
Intersection of FL: a & b
| Parameters: | other (FL) – right hand operand |
|---|---|
| Raises FAdoGeneralError: | |
| if both arguments are not FL |
Generates the trivial linear ANFA equivalent to this language
| Return type: | ANFA |
|---|
Reunion of FL: a | b
| Parameters: | other (FL) – right hand operand |
|---|---|
| Return type: | FL |
| Raises FAdoGeneralError: | |
| if both arguments are not FL |
Bases: object
Base class for Acyclic Finite Automata
Note
This is just a container for some common methods. Not to be used directly!!
Evaluates the rank map of a automaton
| Returns: | pair of sets of states by rank map, reverse delta accessability map |
|---|---|
| Return type: | tuple |
The set of leaves, i.e. final states for last symbols of language words
| Returns: | set of leaves |
|---|---|
| Return type: | set |
Acyclic Deterministic Finite Automata class
Make the ADFA complete
| Parameters: | dead (int) – a state to be identified as dead state if one was not identified yet |
|---|---|
| Return type: | ADFA |
Attention
The object is modified in place
Duplicate the basic structure into a new ADFA. Basically a copy.deep.
| Return type: | ADFA |
|---|
Computes the level for each state
| Returns: | levels of states |
|---|---|
| Return type: | dict |
New in version 0.9.8.
Generates a minimal deterministic cover automata from a DFA
| Return type: | DCFA |
|---|
New in version 0.9.8.
See also
Cezar Campeanu, Andrei Päun, and Sheng Yu, An efficient algorithm for constructing minimal cover automata for finite languages, IJFCS
Finds the minimal equivalent ADFA
See also
[TCS 92 pp 181-189] Minimisation of acyclic deterministic automata in linear time, Dominique Revuz
| Returns: | the minimal equivalent ADFA |
|---|---|
| Return type: | ADFA |
Tests if the DFA is minimal
| Parameters: | method – minimization algorithm (here void) |
|---|---|
| Return type: | bool |
Acyclic Nondeterministic Finite Automata class
Merge state s2 into state s1
| Parameters: |
|---|
Note
no attempt is made to check if the merging preserves the language of teh automaton
Attention
the object is modified in place
Unsets a set as final transfering transition to another final :param int st: the state to be ‘moved’ :param int stf: the destination final state
Note
stf must be a ‘last’ final state, i.e., must have no out transitions to anywhere but to a possible dead state
Attention
the object is modified in place
Generates the ADFA recognizing Sigma^i for i<=l :param set Sigma: the alphabet :param int l: length :param bool exact: only the words with exactly that length? :returns: the automaton :rtype: ADFA
Generates a random trie automaton for a binary language of balanced words of a given leght for max word :param int maxL: length of the max word :param set Sigma: alphabet to be used :param bool safe: should a word of size maxl be present in every language? :return: the generated trie automaton :rtype: ADFA
Generates a random trie automaton for a binary language of balanced words of a given length for max word
| Parameters: | |
|---|---|
| Returns: | the generated trie automaton |
| Return type: | ADFA |
Generates a random trie automaton for a finite language with a given length for max word :param int maxL: length of the max word :param set Sigma: alphabet to be used :param bool safe: should a word of size maxl be present in every language? :return: the generated trie automaton :rtype: ADFA
Generates a random trie automaton for a finite (either prefix free or prefix closed) language with a given length for max word :param int maxL: length of the max word :param set Sigma: alphabet to be used :param bool ClosedP: should it be a prefix closed language? :param bool safe: should a word of size maxl be present in every language? :return: the generated trie automaton :rtype: ADFA
Transforms an acyclic DFA into a ADFA
| Parameters: | aut (DFA) – the automaton to be transformed |
|---|---|
| Raises notAcyclic: | |
| if the DFA is not acyclic | |
| Returns: | the converted automaton |
| Return type: | ADFA |
Convert a canonical string representation of a ADFA to a ADFA :param list s: the string in its canonical order :returns: the ADFA :rtype: ADFA
See also
Marco Almeida, Nelma Moreira, and Rogério Reis. Exact generation of minimal acyclic deterministic finite automata. International Journal of Foundations of Computer Science, 19(4):751-765, August 2008.
Graph support
Basic Graph object support and manipulation
Bases: common.Drawable
Graph base class
| Variables: |
|---|
Adds an edge :param int v1: vertex 1 index :param int v2: vertex 2 index :raises GraphError: if edge is loop
Bases: graphs.Graph
Directed graph base class
Draw a transition in Dot Format
| Parameters: | |
|---|---|
| Return type: | str |
Context Free Grammars Manipulation.
Basic context-free grammars manipulation for building uniform random generetors
Bases: object
Class for context-free grammars
| Variables: |
|
|---|
Initialization
| Parameters: | gram – is a list for productions; each production is a tuple (LeftHandside, RightHandside) with LeftHandside nonterminal, RightHandside list of symbols, First production is for start symbol |
|---|
Bases: cfg.CFGrammar
No useless nonterminals or epsilon rules are ALLOWED... Given a CFG grammar description generates one in CNF Then its possible to random generate words of a given size. Before some pre-calculations are nedded.
Bases: cfg.cfgGenerator
Uniform random Generator for reStrings
Uniform random generator for regular expressions. Used without arguments generates an uncollapsible re over {a,b} with size 10. For generate an arbitary re over an alphabet of 10 symbols of size 100: reStringRGenerator (small_alphabet(10),100,reStringRGenerator.g_regular_base)
| Parameters: |
|
|---|
Note
the grammar can have already this symbols
Transforms a list of rules into a grammar description.
| Parameters: |
|
|---|---|
| Returns: | a grammar description |
Random DFA generation
ICDFA Random generation binding
Changed in version 0.9.4: Interface python to the C code
Changed in version 0.9.6: Working with incomplete automata
Changed in version 0.9.8: distinct classes for complete and incomplete ICDFA
Bases: rndfa.ICDFArgen
Complete ICDFA random generator class
This is the class for the uniform random generator for Initially Connected DFAs
| Variables: |
|
|---|
Note
This is an abstract class, not to be used directly
Bases: rndfa.ICDFArgen
Incomplete ICDFA random generator class
| Variables: |
|
|---|---|
| Raises IllegalBias: | |
if a bias >=1 or <=0 is provided |
Several combined operations for DFAs
Deterministic and non-deterministic automata manipulation, conversion and evaluation.
Authors: Rogério Reis & Nelma Moreira
This is part of FAdo project http://fado.dcc.fc.up.pt
Version: 0.9.5
Copyright: 1999-2012 Rogério Reis & Nelma Moreira<EMAIL_ADDRESS>Star of concatenation of two languages: (L1.L2)*
| Parameters: |
|
|---|---|
| Return type: | DFA |
See also
Yuan Gao, Kai Salomaa, and Sheng Yu. ‘The state complexity of two combined operations: Star of catenation and star of reversal’. Fundamenta Informaticae, 83:75–89, Jan 2008.
Concatenation combined with star: (L1.L2*)
| Parameters: |
|
|---|---|
| Return type: | DFA |
See also
Bo Cui, Yuan Gao, Lila Kari, and Sheng Yu. ‘State complexity of two combined operations: Reversal-catenation and star-catenation’. CoRR, abs/1006.4646, 2010.
Star combined with concatenation: (L1*.L2)
| Parameters: |
|
|---|---|
| Return type: | DFA |
See also
Bo Cui, Yuan Gao, Lila Kari, and Sheng Yu. ‘State complexity of catenation combined with star and reversal’. CoRR, abs/1008.1648, 2010
Star of Union of two DFAs: (L1 + L2)*
| Parameters: |
|
|---|---|
| Return type: | DFA |
See also
Arto Salomaa, Kai Salomaa, and Sheng Yu. ‘State complexity of combined operations’. Theor. Comput. Sci., 383(2-3):140–152, 2007.
Star of Intersection of two DFAs: (L1 & L2)*
| Parameters: |
|
|---|---|
| Return type: | DFA |
See also
Arto Salomaa, Kai Salomaa, and Sheng Yu. ‘State complexity of combined operations’. Theor. Comput. Sci., 383(2-3):140–152, 2007.
Star of Intersection of two DFAs: (L1 & L2)*
| Parameters: |
|
|---|---|
| Return type: | DFA |
Union with star: (L1 + L2*)
| Parameters: |
|
|---|---|
| Return type: | DFA |
See also
Yuan Gao and Sheng Yu. ‘State complexity of union and intersection combined with star and reversal’. CoRR, abs/1006.3755, 2010.
Intersection with star: (L1 & L2*)
| Parameters: |
|
|---|---|
| Return type: | DFA |
See also
Yuan Gao and Sheng Yu. ‘State complexity of union and intersection combined with star and reversal’. CoRR, abs/1006.3755, 2010.
Code theory module
New in version 1.0.
Bases: codes.IATProp
Class of trajectoty properties
Constructor
| Parameters: |
|
|---|
Bases: codes.CodeProperty
Input Preserving Transducer Property
| Variables: |
|
|---|
Constructor :param SFT aut: Input preserving transducer
Tests if the language is maximal w.r.t. the property
| Parameters: |
|
|---|---|
| Return type: | bool |
Tests if the language is maximal w.r.t. the property
| Parameters: |
|
|---|---|
| Return type: | bool |
| Raises PropertyNotSatisfied: | |
if not satisfied |
Bases: codes.IPTProp
Input Altering Transducer Property
Constructor :param SFT aut: Input preserving transducer
Bases: codes.TrajProp, codes.FixedProp
Prefix Property
Bases: codes.IPTProp
Error Correcting Property
Tests if the language is maximal w.r.t. the property
| Parameters: |
|
|---|---|
| Return type: | bool |
Satisfaction of the code property by the automaton language
| Parameters: | aut (DFA|NFA) – the automaton |
|---|---|
| Return type: | tuple |
Satisfaction of the property by the automaton language
See also
S. Konstantinidis: Transducers and the Properties of Error-Detection, Error-Correction and Finite-Delay Decodability. Journal Of Universal Computer Science 8 (2002), 278-291.
| Parameters: | aut (DFA|NFA) – the automaton |
|---|---|
| Return type: | bool |
Builds a TrajProp from a string regexp
| Parameters: | |
|---|---|
| Return type: | TrajProp |
Builds a IATProp from a FAdo SFT file
| Parameters: | fname (str) – file name |
|---|---|
| Return type: | IATProp |
Builds a IPTProp from a FAdo SFT file
| Parameters: | fname (str) – file name |
|---|---|
| Return type: | IPTProp |
Builds a IATProp from a FAdo SFT string
| Parameters: | s (str) – string containing SFT |
|---|---|
| Return type: | IATProp |
Builds a IPTProp from a FAdo SFT string
| Parameters: | s (str) – file name |
|---|---|
| Return type: | IPTProp |
Builds an Error Detecting Property
| Parameters: | fname (str) – file name |
|---|---|
| Return type: | ErrDetectProp |
Builds an Error Correcting Property
| Parameters: | fname (str) – file name |
|---|---|
| Return type: | ErrCorrectProp |
Builds an Error Detecting Property from string
| Parameters: | s (str) – transducer string |
|---|---|
| Return type: | ErrDetectProp |
Builds an Error Correcting Property from string
| Parameters: | s (str) – transducer string |
|---|---|
| Return type: | ErrCorrectProp |
Builds a Prefix Code Property
| Parameters: | alphabet (set) – alphabet |
|---|---|
| Return type: | PrefixProp |
Builds a TrajProp from a string regexp
| Parameters: | |
|---|---|
| Return type: | TrajProp |
Compute the edit distance of a given regular language accepted by the NFA via Input-altering transducer.
Attention
language should have at least two words
See also
Lila Kari, Stavros Konstantinidis, Steffen Kopecki, Meng Yang. An efficient algorithm for computing the edit distance of a regular language via input-altering transducers. arXiv:1406.1041 [cs.FL]
| Parameters: | auto (NFA) – language recogniser |
|---|---|
| Returns: | The edit distance of the given regular language plus a witness pair |
| Return type: | tuple |
GRAIL support.
GRAIL formats support. This is an auxiliary module that sould be imported by fa.py
New in version 0.9.4.
Bases: object
A class for Grail execution
Changed in version 0.9.8: tries to initialise execPath from fadorc
Saves a finite automatom definition to a file using Grail format
| Parameters: |
|
|---|
Saves a finite automatom definition to an open file using Grail format
| Parameters: |
|
|---|
FAdo interface language and slave manager
Applications that want to use FAdo as a slave, just to process it objects should use this language to interface with it.
Note
Every object that is supposed to be available through this language, should be defined in objects and should have a method vDescription, returning the following list
1.0. A name of a format (names should be unique)
1.1. The function that returns the string representation of the object in that format
2.0. Name of the command in verso
2.1. A pair, short/long, descriptions of the method
2.2. Number (n) of arguments of the method
2.2+i. The type of the ith argument
2.1+n. The return type None if does not return (in place transformation)
2.2+n. The function implementing the method having a list as arguments
Bases: yappy_parser.Yappy
A parser for FAdo standard automata descriptions
| Variables: |
|
|---|---|
| Parameters: |
|
FAdo system is a set tools for regular languages manipulation.
Regular languages can be represented by regular expressions (regexp) or finite automata, among other formalisms. Finite automata may be deterministic (DFA) or non-deterministic (NFA). In FAdo these representations are implemented as Python classes. A full documentation of all classes and methods is here.
To work with FAdo, after installation, import the following modules on a Python interpreter:
>>> from FAdo.fa import *
>>> from FAdo.reex import *
>>> from FAdo.fio import *
The module fa implements the classes for finite automata and the module reex the classes for regular expressions. The module fio implements methods for IO of automata and related models.
General conventions
Methods which name ends in P test if the object verifies a given property and return True or False.
Finite Automata
The top class for finite automata is the class FA,which has two main subclasses: OFA for one way finite automata and the class TFA for two-way finite automata. The class OFA implements the basic structure of a finite automaton shared by DFAs and NFAs. This class defines the following attributes:
Sigma: the input alphabet (set)
States: the list of states. It is a list such that each state is referred by its index whenever it is used (transitions, Final, etc).
Initial:the initial state (or a set of initial states for NFA). It is an index or list of indexes.
Final: the set of final states. It is a list of indexes.
In general, one should not create instances (objects) of class OFA. The class DFA and NFA implement DFAs and NFAs, respectively. The class GFA implements generalized NFAs that are used in the conversion between finite automata and regular expressions. All three classes inherit from class OFA.
For each class there are special methods for add/delete/modify alphabet symbols, states and transitions.
DFAs
The following example shows how to build a DFA that accepts the words of {0,1}* that are multiples of 3.
>>> m3= DFA()
>>> m3.setSigma(['0','1'])
>>> m3.addState('s1')
>>> m3.addState('s2')
>>> m3.addState('s3')
>>> m3.setInitial(0)
>>> m3.addFinal(0)
>>> m3.addTransition(0, '0', 0)
>>> m3.addTransition(0, '1', 1)
>>> m3.addTransition(1, '0', 2)
>>> m3.addTransition(1, '1', 0)
>>> m3.addTransition(2, '0', 1)
>>> m3.addTransition(2, '1', 2)
It is now possible, for instance, to see the structure of the automaton or to test if a word is accepted by it.
>>> m3
DFA((['s1', 's2', 's3'], ['1', '0'], 's1', ['s1'], "[('s1', '1', 's2'), ('s1', '0', 's1'), ('s2', '1', 's1'), ('s2', '0', 's3'), ('s3', '1', 's3'), ('s3', '0', 's2')]"))
>>> m3.evalWordP("011")
True
>>> m3.evalWordP("1011")
False
>>>
If graphviz is installed it is also possible to display the diagram of an automaton as follows:
>>>m3.display()
Instead of constructing the DFA directly we can load (and save) it in a simple text format. For the previous automaton the description will be:
Then, if this description is saved in file mul3.fa, we have
>>> m3=readFromFile(“mul3.fa”)[0]
As the set of states is represented by a Python list , the list method len can be used to determine the number of states of a FA:
>>> len(m3.States)
3
For the number of Transitions the countTransitions() method must be used
>>> m3.countTransitions()
6
To minimize a DFA any of the minimization algorithms implemented can be used:
>>> min=m3.minimalHopcroft()
In this case, the DFA was already minimal so min has the same number of states as m3.
Several (regularity preserving) operations of DFAs are implemented in FAdo: boolean (union (| or __or__), intersection (& or __and__) and complementation (~ or __invert__)), concatenation (concat), reversal (reversal) and star (star).
>>> u = m3 | ~m3
>>> u
DFA(([(1, 1), (0, 0), (2, 2)], set(['1', '0']), 0,set([0, 1, 2]), {0: {'1': 1, '0': 0}, 1: {'1': 0, '0': 2}, 2:{'1': 2, '0': 1}}))
>>> m = u.minimal()
>>> m
DFA((['(1, 1)'], ['1', '0'], '(1, 1)', ['(1, 1)'], "[('(1, 1)', '1', '(1, 1)'), ('(1, 1)', '0', '(1, 1)')]"))
State names can be renamed in-place using:
>>> m.renameStates(range(len(m)))
DFA(([‘0’], [‘1’, ‘0’], ‘0’, [‘0’], “[(0, ‘1’, 0), (0, ‘0’, 0)]”))
Notice that m recognize all words over the alphabet {0.1}.
It is possible to generate a word recognisable by an automata (witness)
>>> u.witness()
'@epsilon'
In this case this allows to ensure that u recognizes the empty word.
This method is also useful for obtain a witness for the difference of two DFAs (witnessDiff).
To test if two DFAs are equivalent the the operator == (equivalenceP) can be used.
NFAs
NFAs can be built and manipulated in a similar way. There is no distinction between NFAs with and without epsilon-transitions. But it is possible to test if a NFA has epsilon-transitions and convert between a NFA with epsilon-transitions to a (equivalent) NFA without them.
Converting between NFAs and DFAs
The method toDFA allows to convert a NFA to an equivalent DFA by the subset construction method. The method toNFA migrates trivially a DFA to a NFA.
Regular Expressions
A regular expression can be a symbol of the alphabet, the empty set (@epmtyset), the empty word (@epsilon) or the concatenation or the union (+) or the Kleene star (*) of a regular expression. Examples of regular expressions are a+b, (a+ba)*, and (@epsilon+ a)(ba+ab+@emptyset).
The class regexp is the base class for regular expressions and is used to represent an alphabet symbol. The classes epsilon and emptyset are the subclasses used for the empty set and empty word, respectively. Complex regular expressions are concat, disj, and star.
As for DFAs (and NFAs) we can build directly a regular expressions as a Python class:
>>> r = star(disj(regexp("a"),concat(regexp("b"),regexp("a"))))
>>> print r
(a + (b a))*
But we can convert a string to a regexp class or subclass, using the method str2regexp.
>>> r = str2regexp("(a+ba)*")
>>> print r
(a + (b a))*
For regular expressions there are several measures available: alphabetic size, (parse) tree size, string length, number of epsilons and star height. It is also possible to explicitly associate an alphabet to regular expression (even if some symbols do not appear in it) (setSigma)
There are several algebraic properties that can be used to obtain equivalent regular expressions of a smaller size. The method reduced transforms a regular expression into one equivalent without some obvious unnecessary epsilons, emptysets or stars.
Several methods that allows the manipulation of derivatives (or partial derivatives) by a symbol or by a word are implemented. However, the class regexp does not deal with regular expressions module ACI properties (associativity, commutativity and idempotence of the union) (see class xre) , a so it is not possible to obtain all word derivatives of a given regular expression. This is not the case for partial derivatives.
To test if two regular expressions are equivalent the method compare can be used.
>>> r.compare(str2regexp(\"(a*(ba)*a*)*\"))
True
>>>
Converting Finite Automata to Regular Expressions
For pedagogical purposes, it is implemented a recursive method that constructs a regular expression equivalent to a given DFA (regexp).
>>> print m3.regexp()
((0 + ((@epsilon + 0) (0* (@epsilon + 0)))) + ((1 +((@epsilon + 0) (0* 1))) ((1 (0* 1))* (1 + (1 (0*(@epsilon + 0))))))) + (((1 + ((@epsilon + 0) (0* 1)))((1 (0* 1))* 0)) ((1 + (0 ((1 (0* 1))* 0)))* (0 ((1(0* 1))* (1 + (1 (0* (@epsilon + 0))))))))
Methods based on state elimination techniques are usually more efficient, and produces much smaller regular expressions. We have implemented several heuristics for the elimination order.
>>> print m3.reCG()
((0 + (1 1)) + (((1 0) (1 + (0 0))*) (0 1)))*
Converting Regular Expressions to Finite Automata
Several methods to convert between regular expressions and NFAs are implemented. With the Thompson construction a NFA with epsilon transitions is obtained (nfaThompson). Epsilon free NFAs can be obtained by the Glushkov method (Position automata) (nfaPosition,) the partial derivatives method (nfaPD) or by the follow method (nfaFollow). The two last methods usually allows to obtain smaller NFAs.
>>> r.nfaThompson()
NFA((['', '', '', '', '0', '1', '2', '3', '8', '9'], ['a', 'b'], ['8'], ['9'], "[('', '@epsilon', ''), ('', '@epsilon', 0), ('', '@epsilon', '9'), ('', 'a', ''), ('', '@epsilon', ''), (0, 'b', 1), (1, '@epsilon', 2), (2, 'a', 3), (3, '@epsilon', ''), ('8', '@epsilon', ''), ('8', '@epsilon', '9'), ('9', '@epsilon', '8')]"))
>>> r.nfaPosition()
NFA((['Initial', "('a', 1)", "('b', 2)", "('a', 3)"], ['a', 'b'], ['Initial'], ['Initial', "('a', 1)", "('a', 3)"], '[(\'Initial\', \'a\', "(\'a\', 1)"), (\'Initial\', \'b\', "(\'b\', 2)"), ("(\'a\', 1)", \'a\', "(\'a\', 1)"), ("(\'a\', 1)", \'b\', "(\'b\', 2)"), ("(\'b\', 2)", \'a\', "(\'a\', 3)"), ("(\'a\', 3)", \'a\', "(\'a\', 1)"), ("(\'a\', 3)", \'b\', "(\'b\', 2)")]'))
>>> r.nfaPD()
NFA((['(a + (b a))*', 'a (a + (b a))*'], ['a', 'b'], ['(a + (b a))*'], ['(a + (b a))*'], "[(star(disj(regexp(a),concat(regexp(b),regexp(a)))), 'a', star(disj(regexp(a),concat(regexp(b),regexp(a))))), (star(disj(regexp(a),concat(regexp(b),regexp(a)))), 'b', concat(regexp(a),star(disj(regexp(a),concat(regexp(b),regexp(a)))))), (concat(regexp(a),star(disj(regexp(a),concat(regexp(b),regexp(a))))), 'a', star(disj(regexp(a),concat(regexp(b),regexp(a)))))]"))
General Example
Considering the several methods described before it is possible to convert between the different equivalent representations of regular languages, as well to perform several regularity preserving operations.
>>> r.nfaPosition().toDFA().minimal(complete=False)
DFA((['0', '2'], ['a', 'b'], '0', ['0'], "[('0', 'a', '0'), ('0', 'b', '2'), ('2', 'a', '0')]"))
>>> m3 == m3.reCG().nfaPD().toDFA().minimal()
True
>>>
More classes and modules
Several other classes and modules are also available, including:
class ICDFArnd (module rndfa.py): Random DFA generation
class FL (module fl.py): special methods for finite languages
class xre (module xre.py): extended regular expressions
module comboperations.py: implementation of several algorithms for several combined operations with DFAs and NFAs
module grail.py: compatibility with GRAIL
module transducers.py: several classes and methods for transducers


It seems you clicked the wrong button or you decided not to donate to us after all. Great choice
to
be honestly. If you have the money there are better things to do with it anyway.
But let me show you what you are missing out: if you donated to us you would've
received
the best emoji ever alongside your username!
Just kidding, you do whatever you want with your green notes, but we would like you to know that
every penny made from donations are used to pay the monthly bill to our servers. $6 is enough
for
approximately one month.
Contact us if something is wrong.
Send a message
to: {{ admin_username }}


QUESTION #1
The maximum number of requests/second for any unique IP is 3.
Which of the following will match the given statement above?
QUESTION #2
The maximum number of requests for an idle user is 5.
Which of the following will match the given statement above?
QUESTION #3
The maximum number of requests/second for any unique IP is 2.
Which of the following will match the given statement above?
QUESTION #4
The maximum number of requests for an idle user is 4.
Which of the following will match the given statement above?
QUESTION #5
The maximum number of requests/second for any unique IP is 8.
Which of the following will match the given statement above?
QUESTION #6
The maximum number of requests/second for any unique IP is 5 and the maximum number of requests for an idle user is 3.
Which of the following will match the given statement above?
QUESTION #7
The maximum number of requests/second for any unique IP is 4 and the maximum number of requests for an idle user is 7.
Which of the following will match the given statement above?
QUESTION #8
The maximum number of requests/second for any unique IP is 6 and the maximum number of requests for an idle user is 8.
Which of the following will match the given statement above?
QUESTION #9
The maximum number of requests/second for any unique IP is 5 and the maximum number of requests for an idle user is 7.
Which of the following will match the given statement above?
QUESTION #10
The maximum number of requests/second for any unique IP is 9 and the maximum number of requests for an idle user is 6.
Which of the following will match the given statement above?
QUESTION #11
The maximum number of requests/second for any unique IP is 4 and the maximum number of requests for an idle user is 8. The user clicks the button 3 times per second.
Which of the following will be used to check the rate limit status and what will be the result?
QUESTION #12
The maximum number of requests/second for any unique IP is 3 and the maximum number of requests for an idle user is 3. The user clicks the button 5 times per second.
Which of the following will be used to check the rate limit status and what will be the result?
QUESTION #13
The maximum number of requests/second for any unique IP is 1 and the maximum number of requests for an idle user is 4. The user clicks the button 3 times per second.
Which of the following will be used to check the rate limit status and what will be the result?
QUESTION #14
The maximum number of requests/second for any unique IP is 5 and the maximum number of requests for an idle user is 2. The user clicks the button 4 times per second.
Which of the following will be used to check the rate limit status and what will be the result?
QUESTION #15
The maximum number of requests/second for any unique IP is 1 and the maximum number of requests for an idle user is 3. The user clicks the button twice per second.
Which of the following will be used to check the rate limit status and what will be the result?


3 references to EmitDifferenceOnly
Microsoft.PowerShell.Commands.Utility (3)
commands\utility\Compare-Object.cs (3)
226
EmitDifferenceOnly
(differenceEntry);
445
EmitDifferenceOnly
(differenceEntry);
474
EmitDifferenceOnly
(entry);


.Ru .Co .Ba Figure cathode {border-style SrCo oxygen px;} #ffffff;} material perovskite diffraction electrode electrolyte phase temperature cells conductivity resistance electrical fuel neutron parent materials oxide powder shows solid cubic data observed polarization Alonso J.A. LSGM cell collected density high impedance obtained px; reaction reduction unit-cell using values {font-family °C. Materials Measurements Solid Table air atoms compound crystal font-size range tetragonal thermal °C, ()* Fernández-Díaz Fuel M.T. SrCoO compatibility current different double; energy expansion good power refined respect structure superstructure used value (NPD) Cascos Mater. NPD Oxide Rietveld SOFC. atoms. border-color border-width charge chemical conditions diffusion electrochemical factors ions order perovskites present process properties resistance, solid; space spectra structural studied study symmetrical {font-style {font-weight A.L.L., EIS Energy J.A.A., J.A.A.; L.T., P/mmm S.S., Thermal Troncoso USA, V.C., XRD [], bold catalytic cathodes characterization circuit compared constant courier; dense determined electrolyte. em; frequency group, higher lower measured measurements novel open pattern performance prepared presence presented previously pt;} room sample showing sintered suggest temperatures terms transfer transport use


RoScooter
RoChair
RoTrike
Store
Why Row?
News
Support
RoScooter™
Design
Features
Tech Specs
Gallery
Order Now
PDF Brochure


Element canvas is not supported, please update your browser!
Element canvas is not supported, please update your browser!


Places Visted!
Add the places you visited:
Country Name
City Name
Date Visited
Add
Locations:
Country Name:
City Name:
Date Visted:


HEAD
| School | Accomplishment | Years Active | Location | Zip Code |
|---|---|---|---|---|
| Fort Del Pilar Elementary School | Elementary Graduate | June 2003 - March 2009 | Philippine Military Academy, Kias, Baguio City, Benguet. | 2600 |
| Saint Louis High School Of Balatoc Inc. | High School Graduate | June 2009 - March 2013 | Philippine Military Academy, Kias, Baguio City, Benguet. | 2600 |
| Cordillera School of Digital Arts | Certificate of Participation - Summer Traditional Arts Program | March 2013 | Session Road, Baguio City. | 2600 |
| Saint Louis Uiversity | Undergraduate - Bachelor of Science in Civil Engineering | June 2013 - March 2014 | Bonifacio St., Baguio City, Benguet | 2600 |
| University Of Baguio | Undergraduate - Bachelor of Science in Civil Engineering | March 2014 - April 2014 | Assumption Rd., Baguio City, Benguet | 2600 |
| Saint Louis Uiversity | Undergraduate - Bachelor of Science in Architecture | August 2014 - May 2016 | Bonifacio St., Baguio City, Benguet | 2600 |
August 2014 - May 2016 (Undergraduate)
June 2013 - March 2014 (Undergraduate)
June 2009 - March 2013
June 2003 - March 2009
Electronics Engineer
ECE Faculty Instructor
Saint Louis University
Contact Number: +639056200520
Animator
Layout Artist
D'Lens Studios
Contact Number: +639506839227


10,000 Dogs Needed For Aging Research
by Stephanie MlotOld dogs may be able to teach us new tricks.
The Dog Aging Project aims to understand more about the length and strength of canine lifespans.
The initiative—jointly operated by the University of Washington School of Medicine and Texas A&M University College of Veterinary Medicine & Biomedical Sciences—will create a nationwide community of dogs, owners, vets, researchers, and volunteers.
Launched this week at the annual Gerontological Society of America meeting in Austin, Texas, the Dog Aging Project is in full swing.
Pet owners can go online to nominate their pup as a candidate: You will need to provide comprehensive health and lifestyle information about the animal, as well as share its veterinary medical records.
Dogs of all ages, sizes, sexes, and sterilizations living in all types of locations are invited to sign up. Healthy hounds and those with chronic illness will be considered.
“All owners who complete the nomination process will become Dog Aging Project citizen scientists and their dogs will become members of the ‘pack,'” according to co-director Daniel Promislow. “Their information will allow us to begin carrying out important research on aging in dogs.”
Pooches will be followed throughout their lifetime—long or short—as scientists gather information about the 10,000 enrolled animals in an open-data platform.
There are four key goals of the Dog Aging Project:
- Develop tests to measure dogs’ changes in physical function as they grow older
- Integrate genome sequencing data with health measurements and behavioral traits
- Look for molecular predictors of disease, decline, or longevity
- Assess the effects of the drug rapamycin on cognition, heart function, healthspan, and lifespan
The entire project is expected to take at least 10 years.
“Aging is the major cause of the most common diseases, like cancer and heart problems,” according to researcher Matt Kaeberlein, a professor of pathology at the UW School of Medicine. “Dogs age more rapidly than people do and get many of our same diseases of aging, including cognitive decline.”
“This project will contribute broadly to knowledge about aging in dogs and in people,” he added.
The multi-institutional team’s goal is not merely to increase lifespan, but extend healthspan: the period spent free from disease.
“It is important to me that our work benefits dogs directly,” vet Kate Creevy, associate professor at Texas A&M’s College of Veterinary Medicine & Biomedical Sciences, said in a statement. “But our work with dogs has the added value of shedding light on the human aging experience as well.”
After all, improved quality of life in advanced age is a goal most people have for themselves, as well as their pets.
More on Geek.com:


Grey Apocalypse
Version 0.2.2
Simulation speed:
Round length:
Game progress:
| Round 1 | Round 2 | Total | |
|---|---|---|---|
| Progress | |||
| Winner | |||
| Score |
How to play:
Grey Apocalypse is a programming game. This means that two players have to write programs in the GA programming language.
The grey box above is the memory of a simulated computer. When you click on the "Start" button, the game will start, the two programs will be loaded
and executed. A game of GA consists of two rounds. In round 1, program 1 will be white, and program 2 will be black. White always goes first.
In round 2, the two programs will be swapped. The goal of the game for the white program is to make the "memory" as white as possible, while the black
program tries to make the memory as dark as possible. Programs can do this using the commands described below.
There are two example programs available that are loaded by default. You can just press the "Start" button without doing anything else
to see those two programs in action!
Overview of Commands:
+: This command increases the value of the current memory cell.
For the white program, this will make the current memory cell lighter. If this command is run from the black program, the cell will be made darker.
Advanced usage: When a memory cell is 50% grey (the default colour), the + command will be most effective.
When a memory cell is almost completely white or black, the + command is less effective.
Then, it will only increase the value roughly a sixth of what is would increase by if the colour was grey instead of almost completely white or black.
Therefore, it is much more efficient to use the + command when the colour of the current memory cell is as close to grey as possible.
=: This command sets the value of the current memory cell to the average of the surrounding cells.
Advanced usage: This command gets the values of the four surrounding cells.
The value that is "worst" for the current program is removed, and the average of the remaining three values will be the new value of the current memory cell.
For the white program, the value that will be removed is the darkest value, and the black program will remove the lightest value.
^: This command moves the program up one memory cell.
v: This command moves the program down.
<: This command moves the program left.
>: This command moves the program right.
.: This command does nothing (no-op).
infinite { commands }: This is an infinite loop. All commands inside it are run infinitely.
repeat (number) { commands }:
This is a loop that runs its commands a certain number of times.
The number entered in brackets shows how often the commands should be repeated.
while (condition) { commands }: This is a loop that runs its commands while a certain condition is true.
Advanced usage: Every while loop will store the current x and y coordinates when entering the loop and retrieve the memory value
from that position instead of using the current value as the program may have moved in the meantime.
if (condition) { commands }: An if statement will only run its commands if certain condition is true.
Conditions: A condition always consists of a comparator (greater than (>) or less than (<)) and a number.
For example, >5 is a valid condition.
Conditions always compare the value of the current memory cell with the specified number.
In this example, the loop would run its commands while the value of the current memory cell is greater than 5.
Values of memory range from -127 to 127, with 127 being best and -127 being worst.
Therefore, using a condition like < -10 in a while loop will loop while the value of the current memory cell is less than -10.
A note on loop "unrolling": This version of the game will sometimes run an additional command after running a loop command.
This behaviour simulates loop unrolling, removing some of the disadvantages of code like "repeat (5) { + }" over "+++++".
The evaluator will run an additional command in the following situations:
- At the end of an infinite loop
- At the end of while loops, but only if the code inside the loop will be rerun.
- At the end of if statements.
- At the start and end of repeat loops. This means that there is no difference in performance between "repeat (5) { + }" and "+++++".
Here's an example: If you entered the code "while (<60) { + } >", these are the commands that would be run each step:
- Entering while loop
- Increase (the + command)
- Repeat and another increase (the + command). These commands would be run on the same cycle.
- Repeat and increase
- Repeat and increase
- Repeat and increase
- Repeat and exit loop
- Move right
Finally, here is an overview of the performance loss associated with the usage of certain types of loops:
-
Repeat loops: none. Feel free to use repeat loops as much as you want.
There is no reason to manually unroll loops instead of using a repeat loop. - Infinite loops: One cycle is lost when entering an infinite loop, but there is no performance loss when iterating inside one.
-
While loops: One cycle is lost at the start of every while loop.
It does not matter if you were going to enter the loop or if you were going to skip it entirely.
Another cycle is lost when leaving a while loop.
Note that there is no performance loss when iterating inside a while loop.
-
If statements: One cycle is lost for checking if you are going to enter the if statement,
but there is no performance loss at the end of an if statement
To stop programs like "infinite {}" from crashing the game, I changed the interpreter to only skip up to 10 loop instructions per cycle.
After 10 skipped instructions on a single cycle, a program will be stopped and the other program will be allowed to run (for one cycle).
Otherwise, some types of programs would be able to cause a crash.
Changelog:
* 0.2.2: Added an option to change round length
* 0.2.1: Fixed a very minor documentation issue
* 0.2.0: Changed range of numbers from 0 - 255 to -127 - 127.
Changed scoring, maximum score is now 12700 per round, for a total of 25400.
Negative numbers are now supported in your programs.
Changed default programs to improve IE10 compatibility.
Updated documentation
* 0.1.3: Added version number and changelog
* 0.1.2: Changes loop unrolling and improved documentation
* 0.1.1: Added loop unrolling
* 0.1.0: Initial version


Juan Martin Palazzolo
Functional Analyst && Developer
Welcome reader!
This website is my personal project (code at github), where as a blog, I expose programming related stuff.
Without further due KISS.
Functional Analyst && Developer
This website is my personal project (code at github), where as a blog, I expose programming related stuff.
Without further due KISS.


if you're interested in anything listed above, or anything you can dream of, feel free to get in touch. I am more than happy to help where I can whether it be design, audit/review, build, R&D or whatever you may need.
write to me
find me on the socials


{% spaceless %}
We care for your time and budget.
We are a small group of full-stack software engineers and web designers in the Philippines. Our goal is to help you on your development needs and software maintenance. Hire an engineer for your Python/Django needs for as low as $15 hourly rate.


M Rumman Hasan Khan
Chief Executive Officer, Benclayton Inc.
Faraz Ahmed
Chief Finance Officer, Benclayton Inc.
Ahsan Rasheed
Senior Manager, Benclayton Inc.


It is the mission of The Mercy Warehouse to provide food for those in need through the sale of donated goods. We are uniquely able to leverage valuable community and corporate relationships, causing every dollar that we earn in our thrift store to stretch into large quantities of high-quality groceries. We currently feed over 1,000 people every week through our local food bank in Laguna Niguel, our weekly homeless outreaches into Santa Ana and Los Angeles, and through our sponsorship of three orphanages in Tiajuana, Mexico.
We are a volunteer-run organization. Many members of our community give countless hours every week towards seeing the mission of The Mercy Warehouse fulfilled.


X
How much of our identity can be inferred through data? How much of our identity is
informed by data?
The data “footprints” we leave behind can be extremely personal and deeply intertwined with our offline lives. This data can reveal things about the places we frequent, the people we love, our health, our interests, our insecurities. If we look at our Google Search histories, things like searches for ex-lovers, people that have passed away, strange moles, and other such intimate queries may surface.
Ironically, while can be so intimate and personal, on a larger scale it is used by AdTech companies to abstract our identities into marketable categories like age, household income, and parental status, and even categories like
"daughter died in car accident".
The tools found on this site serve to challenge how our data is being used externally to define us while also asking us to look at how our data affects the ways in which we define ourselves.


| COEFFS | D(6) | transformation coefficients (see note) |
|---|
| XZ | D | x zero point |
|---|---|---|
| YZ | D | y zero point |
| XS | D | x scale |
| YS | D | y scale |
| PERP | D | nonperpendicularity (radians) |
| ORIENT | D | orientation (radians) |
x2 = a + bx1 + cy1The sla_DCMPF routine decomposes this transformation into four steps:
y2 = d + ex1 + fy1
SLALIB --- Positional Astronomy Library


Urllu.js is a lookup tool to allow you to redirect users to other pages based on keywords entered by matching them against a pre-loaded JSON dataset of your choosing.
If multiple entries with the same keyword exist, the first will be matched and redirected.
A sample JSON dataset has been included in this demo.


--- layout: post authors: ["Karin Lagesen"] title: "Feedback on Practicum Proposal" date: 2015-12-09 time: "14:00:00" tags: ["Community", "Instructor Training"] questionnaire: https://docs.google.com/forms/d/1tUGvHb3ByzE5Dji8PUD94mI_UaMywER2Cx5J5-b5Y-s/viewform ---
We have wanted for some time to give newly-trained instructors more experience with workshop materials and our teaching methods before sending them into the field. The mentoring committee and other community members have now created a proposal for doing this, and would like to test it out early in 2016 with participants in the two training session that ran this fall. We have therefore created a short questionnaire to find out whether our plan is feasible and takes us in the right direction.
In brief, trainees will be put into groups of 3-4 people and matched with a mentor. Each group will then work through the core lesson materials for Software or Data Carpentry over four weeks (depending on which they plan to teach). Each group will meet weekly with their mentor, who will guide them though the lesson and answer questions on it.
After the four weeks, each trainee will prepare a one-hour lesson, find a local audience such as their lab group or other colleagues, and teach them the lesson. The mentor will help trainee figure out how to present the material, then observe the trainee's teaching (either live or recorded) and give her feedback.
The mentoring program will take 5-8 weeks depending on how quickly each group moves. We expect trainees to spend 3-5 hours/week working on the lessons and 1-2 hours/week preparing and teaching their lesson.
The mentors are obviously crucial to this process, so we are looking for instructors who have taught at least three times to fill this role. Each mentor will be matched with two groups of trainees (depending on time zones and similar factors) Mentors will be given extra training before and during this program on subjects like giving feedback. Mentoring guides for each lesson will also be developed to help guide discussion with groups.
We expect each mentor to spend 1-3 hours/week. All instructors that participate as mentors will be recognized on the Software Carpentry and Data Carpentry web sites. It will also count as teaching a workshop, which makes this a good way of participating in the Carpentry community for those who find traveling difficult.
This proposal is a change that we think will help new instructors. We also think that it will give existing instructors new ways to learn more about teaching, and about our lessons. However, we need your help to make it work, so please take three minutes to answer the questionnaire.
The proposal in its entirety is available here along with comments.


Unblocked Sites
Back To Hub
Credits
Changelog
Alloy
, for the Framework
Angad Tendulkar
<EMAIL_ADDRESS>, for the site and simplification.