Provided by: tcllib_1.14-dfsg-1_all

**NAME**

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

**SYNOPSIS**

package requireTcl8.4package requiresnitpackage requirestruct::listpackage requirestruct::setpackage requiregrammar::fa::op?0.4.1?::grammar::fa::op::constructorcmd::grammar::fa::op::reversefa::grammar::fa::op::completefa?sink?::grammar::fa::op::remove_epsfa::grammar::fa::op::trimfa?what?::grammar::fa::op::determinizefa?mapvar?::grammar::fa::op::minimizefa?mapvar?::grammar::fa::op::complementfa::grammar::fa::op::kleenefa::grammar::fa::op::optionalfa::grammar::fa::op::unionfafb?mapvar?::grammar::fa::op::intersectfafb?mapvar?::grammar::fa::op::differencefafb?mapvar?::grammar::fa::op::concatenatefafb?mapvar?::grammar::fa::op::fromRegexfaregex?over?::grammar::fa::op::toRegexpfa::grammar::fa::op::toRegexp2fa::grammar::fa::op::toTclRegexpregexpsymdict::grammar::fa::op::simplifyRegexpregexp_________________________________________________________________

**DESCRIPTION**

This package provides a number of complex operations on finite automatons (Short: FA), as provided by the packagegrammar::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 packagesgrammar::faandgrammar::fa::interpreterfor that. Another package related to this isgrammar::fa::compilerwhich 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 sectionFINITEAUTOMATONSin packagegrammar::fa.

**API**

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.Structureoperations::grammar::fa::op::constructorcmdThis command has to be called by the user of the package before any other operations is performed, to establish a command which can be used to construct a FA container object. If this is not done several operations will fail as they are unable to construct internal and transient containers to hold state and/or partial results. Any container class using this package for complex operations should set its own class command as the constructor. See packagegrammar::fafor an example.::grammar::fa::op::reversefaReverses thefa. This is done by reversing the direction of all transitions and swapping the sets ofstartandfinalstates. The language offachanges unpredictably.::grammar::fa::op::completefa?sink? Completes thefacomplete, but nothing is done if thefais alreadycomplete. This implies that only the first in a series of multiple consecutive complete operations onfawill perform anything. The remainder will be null operations. The language offais unchanged by this operation. This is done by adding a single new state, thesink, and transitions from all other states to that sink for all symbols they have no transitions for. The sink itself is made complete by adding loop transitions for all symbols. Note: When a FA has epsilon-transitions transitions over a symbol for a state S can be indirect, i.e. not attached directly to S, but to a state in the epsilon-closure of S. The symbols for such indirect transitions count when computing completeness of a state. In other words, these indirectly reached symbols arenotmissing. The argumentsinkprovides the name for the new state and most not be present in thefaif specified. If the name is not specified the command will name the state "sinkn", wherenis set so that there are no collisions with existing states. Note that the sink state isnotusefulby definition. In other words, while the FA becomes complete, it is alsonotusefulin the strict sense as it has a state from which no final state can be reached.::grammar::fa::op::remove_epsfaRemoves all epsilon-transitions from thefain such a manner the the language offais unchanged. However nothing is done if thefais alreadyepsilon-free. This implies that only the first in a series of multiple consecutive complete operations onfawill perform anything. The remainder will be null operations.Note:This operation may cause states to become unreachable or not useful. These states are not removed by this operation. Use::grammar::fa::op::trimfor that instead.::grammar::fa::op::trimfa?what? Removes unwanted baggage fromfa. The legal values forwhatare listed below. The command defaults to!reachable|!usefulif no specific argument was given.!reachableRemoves all states which are not reachable from a start state.!usefulRemoves all states which are unable to reach a final state.!reachable&!useful!(reachable|useful)Removes all states which are not reachable from a start state and are unable to reach a final state.!reachable|!useful!(reachable&useful)Removes all states which are not reachable from a start state or are unable to reach a final state.::grammar::fa::op::determinizefa?mapvar? Makes thefadeterministic without changing the language accepted by thefa. However nothing is done if thefais alreadydeterministic. This implies that only the first in a series of multiple consecutive complete operations onfawill perform anything. The remainder will be null operations. The command will store a dictionary describing the relationship between the new states of the resulting dfa and the states of the input nfa inmapvar, if it has been specified. Keys of the dictionary are the handles for the states of the resulting dfa, values are sets of states from the input nfa.Note: An empty dictionary signals that the command was able to make thefadeterministic without performing a full subset construction, just by removing states and shuffling transitions around (As part of making the FA epsilon-free).Note: The algorithm fails to make the FA deterministic in the technical sense if the FA has no start state(s), because determinism requires the FA to have exactly one start states. In that situation we make a best effort; and the missing start state will be the only condition preventing the generated result from beingdeterministic. It should also be noted that in this case the possibilities for trimming states from the FA are also severely reduced as we cannot declare states unreachable.::grammar::fa::op::minimizefa?mapvar? Creates a FA which accepts the same language asfa, but has a minimal number of states. Uses Brzozowski's method to accomplish this. The command will store a dictionary describing the relationship between the new states of the resulting minimal fa and the states of the input fa inmapvar, if it has been specified. Keys of the dictionary are the handles for the states of the resulting minimal fa, values are sets of states from the input fa.Note: An empty dictionary signals that the command was able to minimize thefawithout having to compute new states. This should happen if and only if the input FA was already minimal.Note: If the algorithm has no start or final states to work with then the result might be technically minimal, but have a very unexpected structure. It should also be noted that in this case the possibilities for trimming states from the FA are also severely reduced as we cannot declare states unreachable.LanguageoperationsAll 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).::grammar::fa::op::complementfaComplementsfa. This is possible if and only iffaiscompleteanddeterministic. The resulting FA accepts the complementary language offa. In other words, all inputs not accepted by the input are accepted by the result, and vice versa. The result will have all states and transitions of the input, and different final states.::grammar::fa::op::kleenefaApplies Kleene's closure tofa. The resulting FA accepts all stringsSfor which we can find a natural numbern(0 inclusive) and stringsA1...Anin the language offasuch thatSis the concatenation ofA1...An. In other words, the language of the result is the infinite union over finite length concatenations over the language offa. The result will have all states and transitions of the input, and new start and final states.::grammar::fa::op::optionalfaMakes thefaoptional. In other words it computes the FA which accepts the language offaand the empty the word (epsilon) as well. The result will have all states and transitions of the input, and new start and final states.::grammar::fa::op::unionfafb?mapvar? Combines the FAsfaandfbsuch that the resulting FA accepts the union of the languages of the two FAs. The result will have all states and transitions of the two input FAs, and new start and final states. All states offbwhich exist infaas well will be renamed, and themapvarwill contain a mapping from the old states offbto the new ones, if present. It should be noted that the result will be non-deterministic, even if the inputs are deterministic.::grammar::fa::op::intersectfafb?mapvar? Combines the FAsfaandfbsuch that the resulting FA accepts the intersection of the languages of the two FAs. In other words, the result will accept a word if and only if the word is accepted by bothfaandfb. The result will be useful, but not necessarily deterministic or minimal. The command will store a dictionary describing the relationship between the new states of the resulting fa and the pairs of states of the input FAs inmapvar, if it has been specified. Keys of the dictionary are the handles for the states of the resulting fa, values are pairs of states from the input FAs. Pairs are represented by lists. The first element in each pair will be a state infa, the second element will be drawn fromfb.::grammar::fa::op::differencefafb?mapvar? Combines the FAsfaandfbsuch that the resulting FA accepts the difference of the languages of the two FAs. In other words, the result will accept a word if and only if the word is accepted byfa, but not byfb. This can also be expressed as the intersection offawith the complement offb. The result will be useful, but not necessarily deterministic or minimal. The command will store a dictionary describing the relationship between the new states of the resulting fa and the pairs of states of the input FAs inmapvar, if it has been specified. Keys of the dictionary are the handles for the states of the resulting fa, values are pairs of states from the input FAs. Pairs are represented by lists. The first element in each pair will be a state infa, the second element will be drawn fromfb.::grammar::fa::op::concatenatefafb?mapvar? Combines the FAsfaandfbsuch that the resulting FA accepts the cross-product of the languages of the two FAs. I.e. a word W will be accepted by the result if there are two words A and B accepted byfa, andfbresp. and W is the concatenation of A and B. The result FA will be non-deterministic.::grammar::fa::op::fromRegexfaregex?over? Generates a non-deterministic FA which accepts the same language as the regular expressionregex. If theoveris specified it is treated as the set of symbols the regular expression and the automaton are defined over. The command will compute the set from the "S" constructors inregexwhenoverwas not specified. This set is important if and only if the complement operator "!" is used inregexas the complementary language of an FA is quite different for different sets of symbols. The regular expression is represented by a nested list, which forms a syntax tree. The following structures are legal: {S x} Atomic regular expression. Everything else is constructed from these. Accepts theSymbol "x". {. A1 A2 ...} Concatenation operator. Accepts the concatenation of the regular expressionsA1,A2, etc.Notethat this operator accepts zero or more arguments. With zero arguments the represented language isepsilon, the empty word. {| A1 A2 ...} Choice operator, also called "Alternative". Accepts all input accepted by at least one of the regular expressionsA1,A2, etc. In other words, the union ofA1,A2.Notethat this operator accepts zero or more arguments. With zero arguments the represented language is theemptylanguage, the language without words. {& A1 A2 ...} Intersection operator, logical and. Accepts all input accepted which is accepted by all of the regular expressionsA1,A2, etc. In other words, the intersection ofA1,A2. {? A} Optionality operator. Accepts the empty word and anything from the regular expressionA. {* A} Kleene closure. Accepts the empty word and any finite concatenation of words accepted by the regular expressionA. {+ A} Positive Kleene closure. Accepts any finite concatenation of words accepted by the regular expressionA, but not the empty word. {! A} Complement operator. Accepts any word not accepted by the regular expressionA. Note that the complement depends on the set of symbol the result should run over. See the discussion of the argumentoverbefore.::grammar::fa::op::toRegexpfaThis command generates and returns a regular expression which accepts the same language as the finite automatonfa. The regular expression is in the format as described above, for::grammar::fa::op::fromRegex.::grammar::fa::op::toRegexp2faThis command has the same functionality as::grammar::fa::op::toRegexp, but uses a different algorithm to simplify the generated regular expressions.::grammar::fa::op::toTclRegexpregexpsymdictThis command generates and returns a regular expression in Tcl syntax for the regular expressionregexp, if that is possible.regexpis in the same format as expected by::grammar::fa::op::fromRegex. The command will fail and throw an error ifregexpcontains complementation and intersection operations. The argumentsymdictis a dictionary mapping symbol names to pairs ofsyntactictypeand Tcl-regexp. If a symbol occurring in theregexpis not listed in this dictionary then single-character symbols are considered to designate themselves whereas multiple-character symbols are considered to be a character class name.::grammar::fa::op::simplifyRegexpregexpThis command simplifies a regular expression by applying the following algorithm first to the main expression and then recursively to all sub-expressions: [1] Convert the expression into a finite automaton. [2] Minimize the automaton. [3] Convert the automaton back to a regular expression. [4] Choose the shorter of original expression and expression from the previous step.

**EXAMPLES**

**BUGS,** **IDEAS,** **FEEDBACK**

This document, and the package it describes, will undoubtedly contain bugs and other problems. Please report such in the categorygrammar_faof theTcllibSFTrackers[http://sourceforge.net/tracker/?group_id=12883]. Please also report any ideas for enhancements you may have for either package and/or documentation.

**KEYWORDS**

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

**CATEGORY**

Grammars and finite automata

**COPYRIGHT**

Copyright (c) 2004-2008 Andreas Kupries <andreas_kupries@users.sourceforge.net>