fado


Namefado JSON
Version 2.1.2 PyPI version JSON
download
home_pagehttps://fado.dcc.fc.up.pt
SummaryA library of tools to manipulate formal languages' representations mainly automata and regular expressions.
upload_time2023-04-06 08:11:11
maintainer
docs_urlNone
authorRogerio Reis
requires_python>=3.10,<4.0
licenseGPL-3.0-or-later
keywords automata theory formal languages regular expressions transducers
VCS
bugtrack_url
requirements No requirements were recorded.
Travis-CI No Travis.
coveralls test coverage No coveralls.
            =============
What is FAdo?
=============

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.

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

* NFA -> DFA: subset construction

* NFA -> RE: recursive method

* GFA -> RE: state elimination, with possible choice of state orderings

* RE -> NFA: Thompson method, Glushkov method, follow, Brzozowski, and partial derivatives.

* For DFAs several minimization algorithms are available: Moore, Hopcroft, and some incremental algorithms. Brzozowski minimization is available for NFAs.

* An algorithm for hyper-minimization of DFAs

* Language equivalence of two DFAs can be determined by reducing their correspondent minimal DFA to a canonical form, or by the Hopcroft and Karp algorithm.

* Enumeration of the first words of a language or all words of a given length (Cross Section)

* Some support for the transition semigroups of DFAs

----------------
Finite Languages
----------------

Special methods for finite languages are available:

* Construction of a ADFA (acyclic finite automata) from a set of words

* Minimization of ADFAs

* Several methods for ADFAs random generation

* Methods for deterministic cover finite automata (DCFA)

-----------
Transducers
-----------

Several methods for transducers in standard form (SFT) are available:

* Rational operations: union, inverse, reversal, composition, concatenation, Star

* Test if a transducer is functional

* Input intersection and Output intersection operations

-----
Codes
-----

A *language property* is a set of languages. Given a property specified by a transducer, several language tests are possible.

* Satisfaction i.e. if a language satisfies the property

* Maximality i.e. the language satisfies the property and is maximal

* Properties implemented by transducers include: input preserving, input altering, trajectories, and fixed properties

* Computation of the edit distance of a regular language, using input altering transducers




            

Raw data

            {
    "_id": null,
    "home_page": "https://fado.dcc.fc.up.pt",
    "name": "fado",
    "maintainer": "",
    "docs_url": null,
    "requires_python": ">=3.10,<4.0",
    "maintainer_email": "",
    "keywords": "automata theory,formal languages,regular expressions,transducers",
    "author": "Rogerio Reis",
    "author_email": "rogerio.reis@fc.up.pt",
    "download_url": "https://files.pythonhosted.org/packages/5a/57/696996834167290dd9c199575a25e818c6a3345facd399a710a7d5e2ebc3/fado-2.1.2.tar.gz",
    "platform": null,
    "description": "=============\nWhat is FAdo?\n=============\n\nThe **FAdo** system aims to provide an open source extensible high-performance software library for the symbolic\nmanipulation of automata and other models of computation.\n\nTo allow high-level programming with complex data structures, easy prototyping of algorithms, and portability\n(to use in computer grid systems for example), are its main features. Our main motivation is the theoretical\nand experimental research, but we have also in mind the construction of a pedagogical tool for teaching automata\ntheory and formal languages.\n\n-----------------\nRegular Languages\n-----------------\n\nIt currently includes most standard operations for the manipulation of regular languages. Regular languages can\nbe represented by regular expressions (RegExp) or finite automata, among other formalisms. Finite automata may\nbe deterministic (DFA), non-deterministic (NFA) or generalized (GFA). In **FAdo** these representations are implemented\nas Python classes.\n\nElementary regular languages operations as union, intersection, concatenation, complementation and reverse are\nimplemented for each class. Also several combined operations are available for specific models.\n\nSeveral conversions between these representations are implemented:\n\n* NFA -> DFA: subset construction\n\n* NFA -> RE: recursive method\n\n* GFA -> RE: state elimination, with possible choice of state orderings\n\n* RE -> NFA: Thompson method, Glushkov method, follow, Brzozowski, and partial derivatives.\n\n* For DFAs several minimization algorithms are available: Moore, Hopcroft, and some incremental algorithms. Brzozowski minimization is available for NFAs.\n\n* An algorithm for hyper-minimization of DFAs\n\n* Language equivalence of two DFAs can be determined by reducing their correspondent minimal DFA to a canonical form, or by the Hopcroft and Karp algorithm.\n\n* Enumeration of the first words of a language or all words of a given length (Cross Section)\n\n* Some support for the transition semigroups of DFAs\n\n----------------\nFinite Languages\n----------------\n\nSpecial methods for finite languages are available:\n\n* Construction of a ADFA (acyclic finite automata) from a set of words\n\n* Minimization of ADFAs\n\n* Several methods for ADFAs random generation\n\n* Methods for deterministic cover finite automata (DCFA)\n\n-----------\nTransducers\n-----------\n\nSeveral methods for transducers in standard form (SFT) are available:\n\n* Rational operations: union, inverse, reversal, composition, concatenation, Star\n\n* Test if a transducer is functional\n\n* Input intersection and Output intersection operations\n\n-----\nCodes\n-----\n\nA *language property* is a set of languages. Given a property specified by a transducer, several language tests are possible.\n\n* Satisfaction i.e. if a language satisfies the property\n\n* Maximality i.e. the language satisfies the property and is maximal\n\n* Properties implemented by transducers include: input preserving, input altering, trajectories, and fixed properties\n\n* Computation of the edit distance of a regular language, using input altering transducers\n\n\n\n",
    "bugtrack_url": null,
    "license": "GPL-3.0-or-later",
    "summary": "A library of tools to manipulate formal languages' representations  mainly automata and regular expressions.",
    "version": "2.1.2",
    "split_keywords": [
        "automata theory",
        "formal languages",
        "regular expressions",
        "transducers"
    ],
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "blake2b_256": "239fe65148162ae0d060ac3b1ee77634b069de557fb185089eba1a86bd224d44",
                "md5": "0b40da36cec77c4c70df89e406dba163",
                "sha256": "7fb524312c0797aef373fcb04db7de60ab0844ea3a984b4772a5210ef09a61f7"
            },
            "downloads": -1,
            "filename": "fado-2.1.2-py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "0b40da36cec77c4c70df89e406dba163",
            "packagetype": "bdist_wheel",
            "python_version": "py3",
            "requires_python": ">=3.10,<4.0",
            "size": 172434,
            "upload_time": "2023-04-06T08:11:08",
            "upload_time_iso_8601": "2023-04-06T08:11:08.937502Z",
            "url": "https://files.pythonhosted.org/packages/23/9f/e65148162ae0d060ac3b1ee77634b069de557fb185089eba1a86bd224d44/fado-2.1.2-py3-none-any.whl",
            "yanked": false,
            "yanked_reason": null
        },
        {
            "comment_text": "",
            "digests": {
                "blake2b_256": "5a57696996834167290dd9c199575a25e818c6a3345facd399a710a7d5e2ebc3",
                "md5": "d81aa5228ce13f96053b94354a032dac",
                "sha256": "94b08c7e3a818ee74ac31394760d08e9ec76196871278feec032203b53c69771"
            },
            "downloads": -1,
            "filename": "fado-2.1.2.tar.gz",
            "has_sig": false,
            "md5_digest": "d81aa5228ce13f96053b94354a032dac",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": ">=3.10,<4.0",
            "size": 155972,
            "upload_time": "2023-04-06T08:11:11",
            "upload_time_iso_8601": "2023-04-06T08:11:11.239128Z",
            "url": "https://files.pythonhosted.org/packages/5a/57/696996834167290dd9c199575a25e818c6a3345facd399a710a7d5e2ebc3/fado-2.1.2.tar.gz",
            "yanked": false,
            "yanked_reason": null
        }
    ],
    "upload_time": "2023-04-06 08:11:11",
    "github": false,
    "gitlab": false,
    "bitbucket": false,
    "lcname": "fado"
}
        
Elapsed time: 0.05931s