Tcl Library Source Code

Bounty program for improvements to Tcl and certain Tcl packages.

[ Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]


grammar::fa::op - Operations on finite automatons

Table Of Contents


package require Tcl 8.4
package require snit
package require struct::list
package require struct::set
package require grammar::fa::op ?0.4.1?

::grammar::fa::op::constructor cmd
::grammar::fa::op::reverse fa
::grammar::fa::op::complete fa ?sink?
::grammar::fa::op::remove_eps fa
::grammar::fa::op::trim fa ?what?
::grammar::fa::op::determinize fa ?mapvar?
::grammar::fa::op::minimize fa ?mapvar?
::grammar::fa::op::complement fa
::grammar::fa::op::kleene fa
::grammar::fa::op::optional fa
::grammar::fa::op::union fa fb ?mapvar?
::grammar::fa::op::intersect fa fb ?mapvar?
::grammar::fa::op::difference fa fb ?mapvar?
::grammar::fa::op::concatenate fa fb ?mapvar?
::grammar::fa::op::fromRegex fa regex ?over?
::grammar::fa::op::toRegexp fa
::grammar::fa::op::toRegexp2 fa
::grammar::fa::op::toTclRegexp regexp symdict
::grammar::fa::op::simplifyRegexp regexp


This package provides a number of complex operations on finite automatons (Short: FA), as provided by the package grammar::fa. The package does not provide the ability to create and/or manipulate such FAs, nor the ability to execute a FA for a stream of symbols. Use the packages grammar::fa and grammar::fa::interpreter for that. Another package related to this is grammar::fa::compiler which turns a FA into an executor class which has the definition of the FA hardwired into it.

For more information about what a finite automaton is see section FINITE AUTOMATONS in package grammar::fa.


The package exports the API described here. All commands modify their first argument. I.e. whatever FA they compute is stored back into it. Some of the operations will construct an automaton whose states are all new, but related to the states in the source automaton(s). These operations take variable names as optional arguments where they will store mappings which describe the relationship(s). The operations can be loosely partitioned into structural and language operations. The latter are defined in terms of the language the automaton(s) accept, whereas the former are defined in terms of the structural properties of the involved automaton(s). Some operations are both. Structure operations

Language operations All operations in this section require that all input FAs have at least one start and at least one final state. Otherwise the language of the FAs will not be defined, making the operation senseless (as it operates on the languages of the FAs in a defined manner).


Bugs, Ideas, Feedback

This document, and the package it describes, will undoubtedly contain bugs and other problems. Please report such in the category grammar_fa of the Tcllib Trackers. Please also report any ideas for enhancements you may have for either package and/or documentation.

When proposing code changes, please provide unified diffs, i.e the output of diff -u.

Note further that attachments are strongly preferred over inlined patches. Attachments can be made by going to the Edit form of the ticket immediately after its creation, and then using the left-most button in the secondary navigation bar.


automaton, finite automaton, grammar, parsing, regular expression, regular grammar, regular languages, state, transducer


Grammars and finite automata


Copyright © 2004-2008 Andreas Kupries