grammar::fa(3tcl)

📦
version 2.0 · 2 versions
, in debian trixie, ubuntu questing, ubuntu resolute, ubuntu stonking

✨ grammar::fa(3tcl) ✨ — Finite automaton operations and usage 💖

Hey bestie! This is the manual page for grammar::fa, aka the Tcl package that lets you create and manipulate finite automatons. It's giving automaton core energy. No cap. 🦋

🌸 NAME 🌸

grammar::fa — Create and manipulate finite automatons

🎀 SYNOPSIS 🎀

package require Tcl 8.5 9

package require snit 1.3

package require struct::list

package require struct::set

package require grammar::fa::op ?0.3?

package require grammar::fa ?0.6?

::grammar::fa faName ?=|:=|<--|as|deserialize src|fromRegex re ?over??

faName option ?arg arg ...?

faName destroy

faName clear

faName = srcFA

faName --> dstFA

faName serialize

faName deserialize serialization

faName states

faName state add s1 ?s2 ...?

faName state delete s1 ?s2 ...?

faName state exists s

faName state rename s snew

faName startstates

faName start add s1 ?s2 ...?

faName start remove s1 ?s2 ...?

faName start? s

faName start?set stateset

faName finalstates

faName final add s1 ?s2 ...?

faName final remove s1 ?s2 ...?

faName final? s

faName final?set stateset

faName symbols

faName symbols@ s ?d?

faName symbols@set stateset

faName symbol add sym1 ?sym2 ...?

faName symbol delete sym1 ?sym2 ...?

faName symbol rename sym newsym

faName symbol exists sym

faName next s sym ?--> next?

faName !next s sym ?--> next?

faName nextset stateset sym

faName is deterministic

faName is complete

faName is useful

faName is epsilon-free

faName reachable_states

faName unreachable_states

faName reachable s

faName useful_states

faName unuseful_states

faName useful s

faName epsilon_closure s

faName reverse

faName complete

faName remove_eps

faName trim ?what?

faName determinize ?mapvar?

faName minimize ?mapvar?

faName complement

faName kleene

faName optional

faName union fa ?mapvar?

faName intersect fa ?mapvar?

faName difference fa ?mapvar?

faName concatenate fa ?mapvar?

faName fromRegex regex ?over?

🦋 DESCRIPTION 🦋

Okay so this package is literally a container class for finite automatons (short: FA). 💅 It lets you incrementally define the automaton, manipulate it, and query the definition. While it provides complex operations on the automaton (via the package grammar::fa::op), it does not have the ability to execute a definition for a stream of symbols. For that you need the packages grammar::fa::dacceptor and grammar::fa::dexec. Another related package is grammar::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 info about what a finite automaton actually is, see the section FINITE AUTOMATONS. (It's coming later, bestie, don't worry. 😌)

💅 API 💅

The package exports the API described here. Slay.

::grammar::fa faName ?=|:=|<--|as|deserialize src|fromRegex re ?over??

Creates a new finite automaton with an associated global Tcl command whose name is faName. This command may be used to invoke various operations on the automaton. It has the following general form:

faName option ?arg arg ...?

Option and the args determine the exact behavior of the command. See section FA METHODS for more explanations. The new automaton will be empty if no src is specified. Otherwise it will contain a copy of the definition contained in the src. The src has to be a FA object reference for all operators except deserialize and fromRegex. The deserialize operator requires src to be the serialization of a FA instead, and fromRegex takes a regular expression in the form a of a syntax tree. See ::grammar::fa::op::fromRegex for more detail on that.

👑 FA METHODS 👑

All automatons provide the following methods for their manipulation. Periodt. 💖

faName destroy

Destroys the automaton, including its storage space and associated command.

faName clear

Clears out the definition of the automaton contained in faName, but does not destroy the object.

faName = srcFA

Assigns the contents of the automaton contained in srcFA to faName, overwriting any existing definition. This is the assignment operator for automatons. It copies the automaton contained in the FA object srcFA over the automaton definition in faName. The old contents of faName are deleted by this operation.

This operation is in effect equivalent to

faName deserialize [srcFA serialize]

faName --> dstFA

This is the reverse assignment operator for automatons. It copies the automation contained in the object faName over the automaton definition in the object dstFA. The old contents of dstFA are deleted by this operation.

This operation is in effect equivalent to

dstFA deserialize [faName serialize]

faName serialize

This method serializes the automaton stored in faName. In other words it returns a tcl value completely 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 the grammar::fa interface. 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 string grammar::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 is true then the state is a start state, otherwise it is not.
  2. A boolean flag. If its value is true then 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 here.

faName deserialize serialization

This is the complement to serialize. It replaces the automaton definition in faName with the automaton described by the serialization value. The old contents of faName are deleted by this operation.

faName states

Returns the set of all states known to faName.

faName state add s1 ?s2 ...?

Adds the states s1, s2, et cetera to the FA definition in faName. The operation will fail any of the new states is already declared.

faName state delete s1 ?s2 ...?

Deletes the state s1, s2, et cetera, and all associated information from the FA definition in faName. 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 state s is not known to the FA.

faName state exists s

A predicate. It tests whether the state s is known to the FA in faName. The result is a boolean value. It will be set to true if the state s is known, and false otherwise.

faName state rename s snew

Renames the state s to snew. Fails if s is not a known state. Also fails if snew is already known as a state.

faName startstates

Returns the set of states which are marked as start states, also known as initial states. See FINITE AUTOMATONS for explanations what this means.

faName start add s1 ?s2 ...?

Mark the states s1, s2, et cetera in the FA faName as start (aka initial).

faName start remove s1 ?s2 ...?

Mark the states s1, s2, et cetera in the FA faName as not start (aka not accepting).

faName start? s

A predicate. It tests if the state s in the FA faName is start or not. The result is a boolean value. It will be set to true if the state s is start, and false otherwise.

faName start?set stateset

A predicate. It tests if the set of states stateset contains 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 to true if a start state is present in stateset, and false otherwise.

faName finalstates

Returns the set of states which are marked as final states, also known as accepting states. See FINITE AUTOMATONS for explanations what this means.

faName final add s1 ?s2 ...?

Mark the states s1, s2, et cetera in the FA faName as final (aka accepting).

faName final remove s1 ?s2 ...?

Mark the states s1, s2, et cetera in the FA faName as not final (aka not accepting).

faName final? s

A predicate. It tests if the state s in the FA faName is final or not. The result is a boolean value. It will be set to true if the state s is final, and false otherwise.

  • faName final?set stateset — okay so this one's a predicate 🎀 it tests whether the set of states stateset contains at least one final state. Careful tho: the operation will fail if the set contains an element that isn't a known state. What you get back is a boolean value — true if a final state is present in stateset, false otherwise. periodt.
  • faName symbols — hands you the set of all symbols known to the FA faName. that's it, that's the whole vibe ✨
  • faName symbols@ s ?d? — returns the set of all symbols that state s has transitions for. If the empty symbol is in there, then bestie s has epsilon transitions 🦋. And if you specify two states, the result is the set of symbols which have transitions from s to t. lowkey this set can be totally empty if there are no transitions between the two states you picked.
  • faName symbols@set stateset — returns the set of all symbols for which at least one state in the set of states stateset has transitions. In other words, it's the union of [faName symbols@ s] for all states s in stateset. And if the empty symbol is present, that means at least one state inside stateset has epsilon transitions 💅
  • faName symbol add sym1 ?sym2 ...? — adds the symbols sym1, sym2, et cetera to the FA definition in faName. It will fail if any of the symbols is already declared, and the empty string is not allowed as a value for the symbols. no empty-string shenanigans, we don't do that here 🙈
  • faName symbol delete sym1 ?sym2 ...? — deletes the symbols sym1, sym2 et cetera, and all associated information, from the FA definition in faName. And yes, "all associated information" means every transition using those symbols gets deleted too — it's giving scorched earth 💀. The operation will fail if any of the symbols is not known to the FA.
  • faName symbol rename sym newsym — renames the symbol sym to newsym. Fails if sym isn't a known symbol. Also fails if newsym is already known as a symbol. no name collisions allowed, queen 👑
  • faName symbol exists sym — a predicate 🫶 tests whether the symbol sym is known to the FA in faName. Result is a boolean value: true if sym is known, false otherwise.
  • faName next s sym ?--> next? — define or query transition information. okay this one has two modes, pay attention bestie:

If next is specified, the method adds a transition from the state s to the successor state next labeled with the symbol sym to the FA contained in faName. The operation will fail if s or next are not known states, or if sym is not a known symbol. One exception to that last bit: sym is allowed to be the empty string 🌸 in which case the new transition is an epsilon transition, which will not consume input when traversed. It will also fail if the combination of (s, sym, and next) is already present in the FA. no duplicates, we're not doing that.

If next was not specified, then the method returns the set of states which can be reached from s through a single transition labeled with symbol sym. query mode unlocked ⭐

  • faName !next s sym ?--> next? — removes one or more transitions from the FA in faName. here's how it goes down:

If next was specified, the single transition from state s to state next labeled with symbol sym gets removed from the FA. Otherwise, all transitions originating in state s and labeled with symbol sym will be removed. bye bye 👋

The operation will fail if s and/or next are not known as states. It'll also fail if a non-empty sym is not known as a symbol. The empty string is acceptable, and lets you remove epsilon transitions. iconic.

  • faName nextset stateset sym — returns the set of states which can be reached by a single transition originating in a state in the set stateset and labeled with the symbol sym.

In other words, it's the union of [faName next s symbol] for all states s in stateset. yes bestie, it's just vibes math 💖

  • faName is deterministic — a predicate. Tests whether the FA in faName is a deterministic FA or not. Result is a boolean value: true if the FA is deterministic, false otherwise.
  • faName is complete — a predicate. Tests whether the FA in faName is a complete FA or not. A FA is complete if it has at least one transition per state and symbol. Which also means a FA without symbols, or states, is also complete 🎀 (yes, technically empty = complete, we don't make the rules). The result is a boolean value. It will be set to true if the FA is deterministic, and false otherwise.
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. don't forget that part or your math is gonna be off 😭
  • faName is useful — a predicate. Tests whether the FA in faName is a useful FA or not. A FA is useful if all states are reachable and useful. The result is a boolean value. It will be set to true if the FA is deterministic, and false otherwise.
  • faName is epsilon-free — a predicate. Tests whether the FA in faName is an epsilon-free FA or not. A FA is epsilon-free if it has no epsilon transitions. This definition means 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 to true if the FA is deterministic, and false otherwise.
  • faName reachable_states — returns the set of states which are reachable from a start state by one or more transitions. go little states go 🦋
  • faName unreachable_states — returns the set of states which are not reachable from any start state by any number of transitions. This is:
[faName states] - [faName reachable_states]
  • faName reachable s — a predicate. Tests whether the state s in the FA faName can be reached from a start state by one or more transitions. Result is a boolean value: true if the state can be reached, false otherwise.
  • faName useful_states — returns the set of states which are able to reach a final state by one or more transitions. main character states only 💅
  • faName unuseful_states — returns 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]
  • faName useful s — a predicate. Tests whether the state s in the FA faName is able to reach a final state by one or more transitions. Result is a boolean value: true if the state is useful, false otherwise.
  • faName epsilon_closure s — returns the set of states which are reachable from the state s in the FA faName by one or more epsilon transitions, i.e. transitions over the empty symbol, transitions which do not consume input. This is called the epsilon closure of s. fancy name, simple concept, slay ✨
  • faName reverse
  • faName complete
  • faName remove_eps
  • faName trim ?what?
  • faName determinize ?mapvar?
  • faName minimize ?mapvar?
  • faName complement
  • faName kleene
  • faName optional
  • faName union fa ?mapvar?
  • faName intersect fa ?mapvar?
  • faName difference fa ?mapvar?
  • faName concatenate fa ?mapvar?
  • faName fromRegex regex ?over? — these methods provide the more complex operations on the FA 👑. Please see the same-named commands in the package grammar::fa::op for 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 of states,
  • Sy a set of input symbols,
  • St is a subset of S, the set of start states, also known as initial states.
  • Fi is a subset of S, the set of final states, also known as accepting.
  • T is a function from S x (Sy + epsilon) to {S}, the transition function. Here epsilon denotes 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 of successor states.

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 to accept a 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 the language of the FA. One important equivalence is that the set of languages which can be accepted by an FA is the set of regular languages. that's the iconic theorem right there ⭐

Another important concept is that of deterministic FAs. A FA is said to be deterministic if 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). ngl that's such a glow-up 💅

While one of the premier applications of FAs is in parsing, especially in the lexer stage (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 a finite transducer, which has an additional set OSy of output symbols and also an additional output function O 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". yup, output can literally be running code 🫶

Transducers are not handled by this package. They will get their own package in the future.

🐛 BUGS, IDEAS, FEEDBACK 🫶

Okay bestie, real talk: this doc? The package it describes? They will undoubtedly have bugs and other problems. Not "maybe", not "in edge cases" — the manpage itself is telling on itself here, and honestly? Respect for the honesty. 😭

So if you find something cursed, please report it in the category grammar_fa of the Tcllib Trackers:

http://core.tcl.tk/tcllib/reportlist

And not just bugs, okay? Ideas for enhancements are so welcome too — for the package itself and/or the documentation, either one, both, whatever your heart says. 💖

📮 If you're sliding in with code changes

  • Please provide unified diffs — literally the output of diff -u. That's the format, that's the vibe, don't freestyle it. ✨
Heads up though: attachments are strongly preferred over inlined patches. And yes, attaching is easy — right after you create the ticket, go to its Edit form, then hit the left-most button in the secondary navigation bar. That's the one. You got this. 🎀

🔑 KEYWORDS ✨

The searchable little ✨vibes✨ attached to this page, in original order, no cap:

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

🗂️ CATEGORY 🌸

Grammars and finite automata — that's the whole category, that's where this page lives, periodt. 👑

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

And that's a wrap on grammar::fa, bestie! This lil' masterpiece ships as part of tcllib, version 0.6, and the page is dated grammar::fa(3tcl). Go build some automata, you absolute icon. 🦋💖✨

📦 where this page comes from