Provided by: tcllib_1.14-dfsg-1_all

**NAME**

grammar::fa - Create and manipulate finite automatons

**SYNOPSIS**

package requireTcl8.4package requiresnit1.3package requirestruct::listpackage requirestruct::setpackage requiregrammar::fa::op?0.2?package requiregrammar::fa?0.4?::grammar::fafaName?=|:=|<--|as|deserializesrc|fromRegexre?over??faNameoption?argarg...?faNamedestroyfaNameclearfaName=srcFAfaName-->dstFAfaNameserializefaNamedeserializeserializationfaNamestatesfaNamestateadds1?s2...?faNamestatedeletes1?s2...?faNamestateexistssfaNamestaterenamessnewfaNamestartstatesfaNamestartadds1?s2...?faNamestartremoves1?s2...?faNamestart?sfaNamestart?setstatesetfaNamefinalstatesfaNamefinaladds1?s2...?faNamefinalremoves1?s2...?faNamefinal?sfaNamefinal?setstatesetfaNamesymbolsfaNamesymbols@s?d?faNamesymbols@setstatesetfaNamesymboladdsym1?sym2...?faNamesymboldeletesym1?sym2...?faNamesymbolrenamesymnewsymfaNamesymbolexistssymfaNamenextssym?-->next?faName!nextssym?-->next?faNamenextsetstatesetsymfaNameisdeterministicfaNameiscompletefaNameisusefulfaNameisepsilon-freefaNamereachable_statesfaNameunreachable_statesfaNamereachablesfaNameuseful_statesfaNameunuseful_statesfaNameusefulsfaNameepsilon_closuresfaNamereversefaNamecompletefaNameremove_epsfaNametrim?what?faNamedeterminize?mapvar?faNameminimize?mapvar?faNamecomplementfaNamekleenefaNameoptionalfaNameunionfa?mapvar?faNameintersectfa?mapvar?faNamedifferencefa?mapvar?faNameconcatenatefa?mapvar?faNamefromRegexregex?over? _________________________________________________________________

**DESCRIPTION**

This package provides a container class forfiniteautomatons(Short: FA). It allows the incremental definition of the automaton, its manipulation and querying of the definition. While the package provides complex operations on the automaton (via packagegrammar::fa::op), it does not have the ability to execute a definition for a stream of symbols. Use the packagesgrammar::fa::dacceptorandgrammar::fa::dexecfor that. Another package related to this isgrammar::fa::compiler. It turns a FA into an executor class which has the definition of the FA hardwired into it. The output of this package is configurable to suit a large number of different implementation languages and paradigms. For more information about what a finite automaton is see sectionFINITEAUTOMATONS.

**API**

The package exports the API described here.::grammar::fafaName?=|:=|<--|as|deserializesrc|fromRegexre?over?? Creates a new finite automaton with an associated global Tcl command whose name isfaName. This command may be used to invoke various operations on the automaton. It has the following general form:faNameoption?argarg...?Optionand theargs determine the exact behavior of the command. See sectionFAMETHODSfor more explanations. The new automaton will be empty if nosrcis specified. Otherwise it will contain a copy of the definition contained in thesrc. Thesrchas to be a FA object reference for all operators exceptdeserializeandfromRegex. Thedeserializeoperator requiressrcto be the serialization of a FA instead, andfromRegextakes a regular expression in the form a of a syntax tree. See::grammar::fa::op::fromRegexfor more detail on that.

**FA** **METHODS**

All automatons provide the following methods for their manipulation:faNamedestroyDestroys the automaton, including its storage space and associated command.faNameclearClears out the definition of the automaton contained infaName, but doesnotdestroy the object.faName=srcFAAssigns the contents of the automaton contained insrcFAtofaName, overwriting any existing definition. This is the assignment operator for automatons. It copies the automaton contained in the FA objectsrcFAover the automaton definition infaName. The old contents offaNameare deleted by this operation. This operation is in effect equivalent tofaNamedeserialize[srcFAserialize]faName-->dstFAThis is the reverse assignment operator for automatons. It copies the automation contained in the objectfaNameover the automaton definition in the objectdstFA. The old contents ofdstFAare deleted by this operation. This operation is in effect equivalent todstFAdeserialize[faNameserialize]faNameserializeThis method serializes the automaton stored infaName. In other words it returns a tclvaluecompletely describing that automaton. This allows, for example, the transfer of automatons over arbitrary channels, persistence, etc. This method is also the basis for both the copy constructor and the assignment operator. The result of this method has to be semantically identical over all implementations of thegrammar::fainterface. This is what will enable us to copy automatons between different implementations of the same interface. The result is a list of three elements with the following structure: [1] The constant stringgrammar::fa. [2] A list containing the names of all known input symbols. The order of elements in this list is not relevant. [3] The last item in the list is a dictionary, however the order of the keys is important as well. The keys are the states of the serialized FA, and their order is the order in which to create the states when deserializing. This is relevant to preserve the order relationship between states. The value of each dictionary entry is a list of three elements describing the state in more detail. [1] A boolean flag. If its value istruethen the state is a start state, otherwise it is not. [2] A boolean flag. If its value istruethen the state is a final state, otherwise it is not. [3] The last element is a dictionary describing the transitions for the state. The keys are symbols (or the empty string), and the values are sets of successor states. Assuming the following FA (which describes the life of a truck driver in a very simple way :) Drive -- yellow --> Brake -- red --> (Stop) -- red/yellow --> Attention -- green --> Drive (...) is the start state. a possible serialization is grammar::fa \\ {yellow red green red/yellow} \\ {Drive {0 0 {yellow Brake}} \\ Brake {0 0 {red Stop}} \\ Stop {1 0 {red/yellow Attention}} \\ Attention {0 0 {green Drive}}} A possible one, because I did not care about creation order herefaNamedeserializeserializationThis is the complement toserialize. It replaces the automaton definition infaNamewith the automaton described by theserializationvalue. The old contents offaNameare deleted by this operation.faNamestatesReturns the set of all states known tofaName.faNamestateadds1?s2...? Adds the statess1,s2, et cetera to the FA definition infaName. The operation will fail any of the new states is already declared.faNamestatedeletes1?s2...? Deletes the states1,s2, et cetera, and all associated information from the FA definition infaName. The latter means that the information about in- or outbound transitions is deleted as well. If the deleted state was a start or final state then this information is invalidated as well. The operation will fail if the statesis not known to the FA.faNamestateexistssA predicate. It tests whether the statesis known to the FA infaName. The result is a boolean value. It will be set totrueif the statesis known, andfalseotherwise.faNamestaterenamessnewRenames the statestosnew. Fails ifsis not a known state. Also fails ifsnewis already known as a state.faNamestartstatesReturns the set of states which are marked asstartstates, also known asinitialstates. SeeFINITEAUTOMATONSfor explanations what this means.faNamestartadds1?s2...? Mark the statess1,s2, et cetera in the FAfaNameasstart(akainitial).faNamestartremoves1?s2...? Mark the statess1,s2, et cetera in the FAfaNameasnotstart(akanotaccepting).faNamestart?sA predicate. It tests if the statesin the FAfaNameisstartor not. The result is a boolean value. It will be set totrueif the statesisstart, andfalseotherwise.faNamestart?setstatesetA predicate. It tests if the set of statesstatesetcontains at least one start state. They operation will fail if the set contains an element which is not a known state. The result is a boolean value. It will be set totrueif a start state is present instateset, andfalseotherwise.faNamefinalstatesReturns the set of states which are marked asfinalstates, also known asacceptingstates. SeeFINITEAUTOMATONSfor explanations what this means.faNamefinaladds1?s2...? Mark the statess1,s2, et cetera in the FAfaNameasfinal(akaaccepting).faNamefinalremoves1?s2...? Mark the statess1,s2, et cetera in the FAfaNameasnotfinal(akanotaccepting).faNamefinal?sA predicate. It tests if the statesin the FAfaNameisfinalor not. The result is a boolean value. It will be set totrueif the statesisfinal, andfalseotherwise.faNamefinal?setstatesetA predicate. It tests if the set of statesstatesetcontains at least one final state. They operation will fail if the set contains an element which is not a known state. The result is a boolean value. It will be set totrueif a final state is present instateset, andfalseotherwise.faNamesymbolsReturns the set of all symbols known to the FAfaName.faNamesymbols@s?d? Returns the set of all symbols for which the stateshas transitions. If the empty symbol is present thenshas epsilon transitions. If two states are specified the result is the set of symbols which have transitions fromstot. This set may be empty if there are no transitions between the two specified states.faNamesymbols@setstatesetReturns the set of all symbols for which at least one state in the set of statesstatesethas transitions. In other words, the union of [faNamesymbols@s] for all statessinstateset. If the empty symbol is present then at least one state contained instatesethas epsilon transitions.faNamesymboladdsym1?sym2...? Adds the symbolssym1,sym2, et cetera to the FA definition infaName. The operation will fail any of the symbols is already declared. The empty string is not allowed as a value for the symbols.faNamesymboldeletesym1?sym2...? Deletes the symbolssym1,sym2et cetera, and all associated information from the FA definition infaName. The latter means that all transitions using the symbols are deleted as well. The operation will fail if any of the symbols is not known to the FA.faNamesymbolrenamesymnewsymRenames the symbolsymtonewsym. Fails ifsymis not a known symbol. Also fails ifnewsymis already known as a symbol.faNamesymbolexistssymA predicate. It tests whether the symbolsymis known to the FA infaName. The result is a boolean value. It will be set totrueif the symbolsymis known, andfalseotherwise.faNamenextssym?-->next? Define or query transition information. Ifnextis specified, then the method will add a transition from the statesto thesuccessorstatenextlabeled with the symbolsymto the FA contained infaName. The operation will fail ifs, ornextare not known states, or ifsymis not a known symbol. An exception to the latter is thatsymis allowed to be the empty string. In that case the new transition is anepsilontransitionwhich will not consume input when traversed. The operation will also fail if the combination of (s,sym, andnext) is already present in the FA. Ifnextwas not specified, then the method will return the set of states which can be reached fromsthrough a single transition labeled with symbolsym.faName!nextssym?-->next? Remove one or more transitions from the Fa infaName. Ifnextwas specified then the single transition from the statesto the statenextlabeled with the symbolsymis removed from the FA. Otherwisealltransitions originating in statesand labeled with the symbolsymwill be removed. The operation will fail ifsand/ornextare not known as states. It will also fail if a non-emptysymis not known as symbol. The empty string is acceptable, and allows the removal of epsilon transitions.faNamenextsetstatesetsymReturns the set of states which can be reached by a single transition originating in a state in the setstatesetand labeled with the symbolsym. In other words, this is the union of [faNamenextssymbol] for all statessinstateset.faNameisdeterministicA predicate. It tests whether the FA infaNameis a deterministic FA or not. The result is a boolean value. It will be set totrueif the FA is deterministic, andfalseotherwise.faNameiscompleteA predicate. It tests whether the FA infaNameis a complete FA or not. A FA is complete if it has at least one transition per state and symbol. This also means that a FA without symbols, or states is also complete. The result is a boolean value. It will be set totrueif the FA is deterministic, andfalseotherwise. 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.faNameisusefulA predicate. It tests whether the FA infaNameis an useful FA or not. A FA is useful if all states arereachableanduseful. The result is a boolean value. It will be set totrueif the FA is deterministic, andfalseotherwise.faNameisepsilon-freeA predicate. It tests whether the FA infaNameis an epsilon-free FA or not. A FA is epsilon-free if it has no epsilon transitions. This definition means that all deterministic FAs are epsilon-free as well, and epsilon-freeness is a necessary pre-condition for deterministic'ness. The result is a boolean value. It will be set totrueif the FA is deterministic, andfalseotherwise.faNamereachable_statesReturns the set of states which are reachable from a start state by one or more transitions.faNameunreachable_statesReturns the set of states which are not reachable from any start state by any number of transitions. This is [faName states] - [faName reachable_states]faNamereachablesA predicate. It tests whether the statesin the FAfaNamecan be reached from a start state by one or more transitions. The result is a boolean value. It will be set totrueif the state can be reached, andfalseotherwise.faNameuseful_statesReturns the set of states which are able to reach a final state by one or more transitions.faNameunuseful_statesReturns the set of states which are not able to reach a final state by any number of transitions. This is [faName states] - [faName useful_states]faNameusefulsA predicate. It tests whether the statesin the FAfaNameis able to reach a final state by one or more transitions. The result is a boolean value. It will be set totrueif the state is useful, andfalseotherwise.faNameepsilon_closuresReturns the set of states which are reachable from the statesin the FAfaNameby one or more epsilon transitions, i.e transitions over the empty symbol, transitions which do not consume input. This is called theepsilonclosureofs.faNamereversefaNamecompletefaNameremove_epsfaNametrim?what?faNamedeterminize?mapvar?faNameminimize?mapvar?faNamecomplementfaNamekleenefaNameoptionalfaNameunionfa?mapvar?faNameintersectfa?mapvar?faNamedifferencefa?mapvar?faNameconcatenatefa?mapvar?faNamefromRegexregex?over? These methods provide more complex operations on the FA. Please see the same-named commands in the packagegrammar::fa::opfor descriptions of what they do.

**EXAMPLES**

**FINITE** **AUTOMATONS**

For the mathematically inclined, a FA is a 5-tuple (S,Sy,St,Fi,T) where · S is a set ofstates, · Sy a set ofinputsymbols, · St is a subset of S, the set ofstartstates, also known asinitialstates. · Fi is a subset of S, the set offinalstates, also known asaccepting. · T is a function from S x (Sy + epsilon) to {S}, thetransitionfunction. Hereepsilondenotes the empty input symbol and is distinct from all symbols in Sy; and {S} is the set of subsets of S. In other words, T maps a combination of State and Input (which can be empty) to a set ofsuccessorstates. In computer theory a FA is most often shown as a graph where the nodes represent the states, and the edges between the nodes encode the transition function: For all n in S' = T (s, sy) we have one edge between the nodes representing s and n resp., labeled with sy. The start and accepting states are encoded through distinct visual markers, i.e. they are attributes of the nodes. FA's are used to process streams of symbols over Sy. A specific FA is said toaccepta finite stream sy_1 sy_2 ... sy_n if there is a path in the graph of the FA beginning at a state in St and ending at a state in Fi whose edges have the labels sy_1, sy_2, etc. to sy_n. The set of all strings accepted by the FA is thelanguageof the FA. One important equivalence is that the set of languages which can be accepted by an FA is the set ofregularlanguages. Another important concept is that of deterministic FAs. A FA is said to bedeterministicif for each string of input symbols there is exactly one path in the graph of the FA beginning at the start state and whose edges are labeled with the symbols in the string. While it might seem that non-deterministic FAs to have more power of recognition, this is not so. For each non-deterministic FA we can construct a deterministic FA which accepts the same language (--> Thompson's subset construction). While one of the premier applications of FAs is inparsing, especially in thelexerstage (where symbols == characters), this is not the only possibility by far. Quite a lot of processes can be modeled as a FA, albeit with a possibly large set of states. For these the notion of accepting states is often less or not relevant at all. What is needed instead is the ability to act to state changes in the FA, i.e. to generate some output in response to the input. This transforms a FA into afinitetransducer, which has an additional set OSy ofoutputsymbolsand also an additionaloutputfunctionO which maps from "S x (Sy + epsilon)" to "(Osy + epsilon)", i.e a combination of state and input, possibly empty to an output symbol, or nothing. For the graph representation this means that edges are additional labeled with the output symbol to write when this edge is traversed while matching input. Note that for an application "writing an output symbol" can also be "executing some code". Transducers are not handled by this package. They will get their own package in the future.

**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-2009 Andreas Kupries <andreas_kupries@users.sourceforge.net>