1grammar::fa(n) Finite automaton operations and usage grammar::fa(n)
2______________________________________________________________________________
6
8 grammar::fa - Create and manipulate finite automatons
9
11 package require Tcl 8.4
12 package require snit 1.3
14 package require struct::list
16 package require struct::set
18 package require grammar::fa::op ?0.2?
20 package require grammar::fa ?0.4?
22 ::grammar::fa faName ?=|:=|<--|as|deserialize src|fromRegex re ?over??
24 faName option ?arg arg ...?
26 faName destroy
28 faName clear
30 faName = srcFA
32 faName --> dstFA
34 faName serialize
36 faName deserialize serialization
38 faName states
40 faName state add s1 ?s2 ...?
42 faName state delete s1 ?s2 ...?
44 faName state exists s
46 faName state rename s snew
48 faName startstates
50 faName start add s1 ?s2 ...?
52 faName start remove s1 ?s2 ...?
54 faName start? s
56 faName start?set stateset
58 faName finalstates
60 faName final add s1 ?s2 ...?
62 faName final remove s1 ?s2 ...?
64 faName final? s
66 faName final?set stateset
68 faName symbols
70 faName symbols@ s ?d?
72 faName symbols@set stateset
74 faName symbol add sym1 ?sym2 ...?
76 faName symbol delete sym1 ?sym2 ...?
78 faName symbol rename sym newsym
80 faName symbol exists sym
82 faName next s sym ?--> next?
84 faName !next s sym ?--> next?
86 faName nextset stateset sym
88 faName is deterministic
90 faName is complete
92 faName is useful
94 faName is epsilon-free
96 faName reachable_states
98 faName unreachable_states
100 faName reachable s
102 faName useful_states
104 faName unuseful_states
106 faName useful s
108 faName epsilon_closure s
110 faName reverse
112 faName complete
114 faName remove_eps
116 faName trim ?what?
118 faName determinize ?mapvar?
120 faName minimize ?mapvar?
122 faName complement
124 faName kleene
126 faName optional
128 faName union fa ?mapvar?
130 faName intersect fa ?mapvar?
132 faName difference fa ?mapvar?
134 faName concatenate fa ?mapvar?
136 faName fromRegex regex ?over?
138______________________________________________________________________________
140
142 This package provides a container class for finite automatons (Short:
143 FA). It allows the incremental definition of the automaton, its manip‐
144 ulation and querying of the definition. While the package provides
145 complex operations on the automaton (via package grammar::fa::op), it
146 does not have the ability to execute a definition for a stream of sym‐
147 bols. Use the packages grammar::fa::dacceptor and grammar::fa::dexec
148 for that. Another package related to this is grammar::fa::compiler. It
149 turns a FA into an executor class which has the definition of the FA
150 hardwired into it. The output of this package is configurable to suit a
151 large number of different implementation languages and paradigms.
152 For more information about what a finite automaton is see section
154 FINITE AUTOMATONS.
155
157 The package exports the API described here.
158 ::grammar::fa faName ?=|:=|<--|as|deserialize src|fromRegex re ?over??
160 Creates a new finite automaton with an associated global Tcl
161 command whose name is faName. This command may be used to invoke
162 various operations on the automaton. It has the following gen‐
163 eral form:
164 faName option ?arg arg ...?
166 Option and the args determine the exact behavior of the
167 command. See section FA METHODS for more explanations.
168 The new automaton will be empty if no src is specified.
169 Otherwise it will contain a copy of the definition con‐
170 tained in the src. The src has to be a FA object refer‐
171 ence for all operators except deserialize and fromRegex.
172 The deserialize operator requires src to be the serial‐
173 ization of a FA instead, and fromRegex takes a regular
174 expression in the form a of a syntax tree. See ::gram‐
175 mar::fa::op::fromRegex for more detail on that.
176
178 All automatons provide the following methods for their manipulation:
179 faName destroy
181 Destroys the automaton, including its storage space and associ‐
182 ated command.
183 faName clear
185 Clears out the definition of the automaton contained in faName,
186 but does not destroy the object.
187 faName = srcFA
189 Assigns the contents of the automaton contained in srcFA to
190 faName, overwriting any existing definition. This is the
191 assignment operator for automatons. It copies the automaton con‐
192 tained in the FA object srcFA over the automaton definition in
193 faName. The old contents of faName are deleted by this opera‐
194 tion.
195 This operation is in effect equivalent to
197 faName deserialize [srcFA serialize]
201 faName --> dstFA
204 This is the reverse assignment operator for automatons. It
205 copies the automation contained in the object faName over the
206 automaton definition in the object dstFA. The old contents of
207 dstFA are deleted by this operation.
208 This operation is in effect equivalent to
210 dstFA deserialize [faName serialize]
214 faName serialize
217 This method serializes the automaton stored in faName. In other
218 words it returns a tcl value completely describing that automa‐
219 ton. This allows, for example, the transfer of automatons over
220 arbitrary channels, persistence, etc. This method is also the
221 basis for both the copy constructor and the assignment operator.
222 The result of this method has to be semantically identical over
224 all implementations of the grammar::fa interface. This is what
225 will enable us to copy automatons between different implementa‐
226 tions of the same interface.
227 The result is a list of three elements with the following struc‐
229 ture:
230 [1] The constant string grammar::fa.
232 [2] A list containing the names of all known input symbols.
234 The order of elements in this list is not relevant.
235 [3] The last item in the list is a dictionary, however the
237 order of the keys is important as well. The keys are the
238 states of the serialized FA, and their order is the order
239 in which to create the states when deserializing. This is
240 relevant to preserve the order relationship between
241 states.
242 The value of each dictionary entry is a list of three
244 elements describing the state in more detail.
245 [1] A boolean flag. If its value is true then the
247 state is a start state, otherwise it is not.
248 [2] A boolean flag. If its value is true then the
250 state is a final state, otherwise it is not.
251 [3] The last element is a dictionary describing the
253 transitions for the state. The keys are symbols
254 (or the empty string), and the values are sets of
255 successor states.
256 Assuming the following FA (which describes the life of a truck driver
258 in a very simple way :)
259 Drive -- yellow --> Brake -- red --> (Stop) -- red/yellow --> Attention -- green --> Drive
263 (...) is the start state.
264 a possible serialization is
267 grammar::fa \\
271 {yellow red green red/yellow} \\
272 {Drive {0 0 {yellow Brake}} \\
273 Brake {0 0 {red Stop}} \\
274 Stop {1 0 {red/yellow Attention}} \\
275 Attention {0 0 {green Drive}}}
276 A possible one, because I did not care about creation order here
279 faName deserialize serialization
281 This is the complement to serialize. It replaces the automaton
282 definition in faName with the automaton described by the serial‐
283 ization value. The old contents of faName are deleted by this
284 operation.
285 faName states
287 Returns the set of all states known to faName.
288 faName state add s1 ?s2 ...?
290 Adds the states s1, s2, et cetera to the FA definition in
291 faName. The operation will fail any of the new states is already
292 declared.
293 faName state delete s1 ?s2 ...?
295 Deletes the state s1, s2, et cetera, and all associated informa‐
296 tion from the FA definition in faName. The latter means that the
297 information about in- or outbound transitions is deleted as
298 well. If the deleted state was a start or final state then this
299 information is invalidated as well. The operation will fail if
300 the state s is not known to the FA.
301 faName state exists s
303 A predicate. It tests whether the state s is known to the FA in
304 faName. The result is a boolean value. It will be set to true
305 if the state s is known, and false otherwise.
306 faName state rename s snew
308 Renames the state s to snew. Fails if s is not a known state.
309 Also fails if snew is already known as a state.
310 faName startstates
312 Returns the set of states which are marked as start states, also
313 known as initial states. See FINITE AUTOMATONS for explanations
314 what this means.
315 faName start add s1 ?s2 ...?
317 Mark the states s1, s2, et cetera in the FA faName as start (aka
318 initial).
319 faName start remove s1 ?s2 ...?
321 Mark the states s1, s2, et cetera in the FA faName as not start
322 (aka not accepting).
323 faName start? s
325 A predicate. It tests if the state s in the FA faName is start
326 or not. The result is a boolean value. It will be set to true
327 if the state s is start, and false otherwise.
328 faName start?set stateset
330 A predicate. It tests if the set of states stateset contains at
331 least one start state. They operation will fail if the set con‐
332 tains an element which is not a known state. The result is a
333 boolean value. It will be set to true if a start state is
334 present in stateset, and false otherwise.
335 faName finalstates
337 Returns the set of states which are marked as final states, also
338 known as accepting states. See FINITE AUTOMATONS for explana‐
339 tions what this means.
340 faName final add s1 ?s2 ...?
342 Mark the states s1, s2, et cetera in the FA faName as final (aka
343 accepting).
344 faName final remove s1 ?s2 ...?
346 Mark the states s1, s2, et cetera in the FA faName as not final
347 (aka not accepting).
348 faName final? s
350 A predicate. It tests if the state s in the FA faName is final
351 or not. The result is a boolean value. It will be set to true
352 if the state s is final, and false otherwise.
353 faName final?set stateset
355 A predicate. It tests if the set of states stateset contains at
356 least one final state. They operation will fail if the set con‐
357 tains an element which is not a known state. The result is a
358 boolean value. It will be set to true if a final state is
359 present in stateset, and false otherwise.
360 faName symbols
362 Returns the set of all symbols known to the FA faName.
363 faName symbols@ s ?d?
365 Returns the set of all symbols for which the state s has transi‐
366 tions. If the empty symbol is present then s has epsilon tran‐
367 sitions. If two states are specified the result is the set of
368 symbols which have transitions from s to t. This set may be
369 empty if there are no transitions between the two specified
370 states.
371 faName symbols@set stateset
373 Returns the set of all symbols for which at least one state in
374 the set of states stateset has transitions. In other words, the
375 union of [faName symbols@ s] for all states s in stateset. If
376 the empty symbol is present then at least one state contained in
377 stateset has epsilon transitions.
378 faName symbol add sym1 ?sym2 ...?
380 Adds the symbols sym1, sym2, et cetera to the FA definition in
381 faName. The operation will fail any of the symbols is already
382 declared. The empty string is not allowed as a value for the
383 symbols.
384 faName symbol delete sym1 ?sym2 ...?
386 Deletes the symbols sym1, sym2 et cetera, and all associated
387 information from the FA definition in faName. The latter means
388 that all transitions using the symbols are deleted as well. The
389 operation will fail if any of the symbols is not known to the
390 FA.
391 faName symbol rename sym newsym
393 Renames the symbol sym to newsym. Fails if sym is not a known
394 symbol. Also fails if newsym is already known as a symbol.
395 faName symbol exists sym
397 A predicate. It tests whether the symbol sym is known to the FA
398 in faName. The result is a boolean value. It will be set to
399 true if the symbol sym is known, and false otherwise.
400 faName next s sym ?--> next?
402 Define or query transition information.
403 If next is specified, then the method will add a transition from
405 the state s to the successor state next labeled with the symbol
406 sym to the FA contained in faName. The operation will fail if s,
407 or next are not known states, or if sym is not a known symbol.
408 An exception to the latter is that sym is allowed to be the
409 empty string. In that case the new transition is an epsilon
410 transition which will not consume input when traversed. The
411 operation will also fail if the combination of (s, sym, and
412 next) is already present in the FA.
413 If next was not specified, then the method will return the set
415 of states which can be reached from s through a single transi‐
416 tion labeled with symbol sym.
417 faName !next s sym ?--> next?
419 Remove one or more transitions from the Fa in faName.
420 If next was specified then the single transition from the state
422 s to the state next labeled with the symbol sym is removed from
423 the FA. Otherwise all transitions originating in state s and
424 labeled with the symbol sym will be removed.
425 The operation will fail if s and/or next are not known as
427 states. It will also fail if a non-empty sym is not known as
428 symbol. The empty string is acceptable, and allows the removal
429 of epsilon transitions.
430 faName nextset stateset sym
432 Returns the set of states which can be reached by a single tran‐
433 sition originating in a state in the set stateset and labeled
434 with the symbol sym.
435 In other words, this is the union of [faName next s symbol] for
437 all states s in stateset.
438 faName is deterministic
440 A predicate. It tests whether the FA in faName is a determinis‐
441 tic FA or not. The result is a boolean value. It will be set to
442 true if the FA is deterministic, and false otherwise.
443 faName is complete
445 A predicate. It tests whether the FA in faName is a complete FA
446 or not. A FA is complete if it has at least one transition per
447 state and symbol. This also means that a FA without symbols, or
448 states is also complete. The result is a boolean value. It will
449 be set to true if the FA is deterministic, and false otherwise.
450 Note: When a FA has epsilon-transitions transitions over a sym‐
452 bol for a state S can be indirect, i.e. not attached directly to
453 S, but to a state in the epsilon-closure of S. The symbols for
454 such indirect transitions count when computing completeness.
455 faName is useful
457 A predicate. It tests whether the FA in faName is an useful FA
458 or not. A FA is useful if all states are reachable and useful.
459 The result is a boolean value. It will be set to true if the FA
460 is deterministic, and false otherwise.
461 faName is epsilon-free
463 A predicate. It tests whether the FA in faName is an epsilon-
464 free FA or not. A FA is epsilon-free if it has no epsilon tran‐
465 sitions. This definition means that all deterministic FAs are
466 epsilon-free as well, and epsilon-freeness is a necessary pre-
467 condition for deterministic'ness. The result is a boolean
468 value. It will be set to true if the FA is deterministic, and
469 false otherwise.
470 faName reachable_states
472 Returns the set of states which are reachable from a start state
473 by one or more transitions.
474 faName unreachable_states
476 Returns the set of states which are not reachable from any start
477 state by any number of transitions. This is
478 [faName states] - [faName reachable_states]
482 faName reachable s
485 A predicate. It tests whether the state s in the FA faName can
486 be reached from a start state by one or more transitions. The
487 result is a boolean value. It will be set to true if the state
488 can be reached, and false otherwise.
489 faName useful_states
491 Returns the set of states which are able to reach a final state
492 by one or more transitions.
493 faName unuseful_states
495 Returns the set of states which are not able to reach a final
496 state by any number of transitions. This is
497 [faName states] - [faName useful_states]
501 faName useful s
504 A predicate. It tests whether the state s in the FA faName is
505 able to reach a final state by one or more transitions. The
506 result is a boolean value. It will be set to true if the state
507 is useful, and false otherwise.
508 faName epsilon_closure s
510 Returns the set of states which are reachable from the state s
511 in the FA faName by one or more epsilon transitions, i.e transi‐
512 tions over the empty symbol, transitions which do not consume
513 input. This is called the epsilon closure of s.
514 faName reverse
516 faName complete
518 faName remove_eps
520 faName trim ?what?
522 faName determinize ?mapvar?
524 faName minimize ?mapvar?
526 faName complement
528 faName kleene
530 faName optional
532 faName union fa ?mapvar?
534 faName intersect fa ?mapvar?
536 faName difference fa ?mapvar?
538 faName concatenate fa ?mapvar?
540 faName fromRegex regex ?over?
542 These methods provide more complex operations on the FA. Please
543 see the same-named commands in the package grammar::fa::op for
544 descriptions of what they do.
545
548 For the mathematically inclined, a FA is a 5-tuple (S,Sy,St,Fi,T) where
549 · S is a set of states,
551 · Sy a set of input symbols,
553 · St is a subset of S, the set of start states, also known as ini‐
555 tial states.
556 · Fi is a subset of S, the set of final states, also known as
558 accepting.
559 · T is a function from S x (Sy + epsilon) to {S}, the transition
561 function. Here epsilon denotes the empty input symbol and is
562 distinct from all symbols in Sy; and {S} is the set of subsets
563 of S. In other words, T maps a combination of State and Input
564 (which can be empty) to a set of successor states.
565 In computer theory a FA is most often shown as a graph where the nodes
567 represent the states, and the edges between the nodes encode the tran‐
568 sition function: For all n in S' = T (s, sy) we have one edge between
569 the nodes representing s and n resp., labeled with sy. The start and
570 accepting states are encoded through distinct visual markers, i.e. they
571 are attributes of the nodes.
572 FA's are used to process streams of symbols over Sy.
574 A specific FA is said to accept a finite stream sy_1 sy_2 ... sy_n if
576 there is a path in the graph of the FA beginning at a state in St and
577 ending at a state in Fi whose edges have the labels sy_1, sy_2, etc. to
578 sy_n. The set of all strings accepted by the FA is the language of the
579 FA. One important equivalence is that the set of languages which can be
580 accepted by an FA is the set of regular languages.
581 Another important concept is that of deterministic FAs. A FA is said to
583 be deterministic if for each string of input symbols there is exactly
584 one path in the graph of the FA beginning at the start state and whose
585 edges are labeled with the symbols in the string. While it might seem
586 that non-deterministic FAs to have more power of recognition, this is
587 not so. For each non-deterministic FA we can construct a deterministic
588 FA which accepts the same language (--> Thompson's subset construc‐
589 tion).
590 While one of the premier applications of FAs is in parsing, especially
592 in the lexer stage (where symbols == characters), this is not the only
593 possibility by far.
594 Quite a lot of processes can be modeled as a FA, albeit with a possibly
596 large set of states. For these the notion of accepting states is often
597 less or not relevant at all. What is needed instead is the ability to
598 act to state changes in the FA, i.e. to generate some output in
599 response to the input. This transforms a FA into a finite transducer,
600 which has an additional set OSy of output symbols and also an addi‐
601 tional output function O which maps from "S x (Sy + epsilon)" to "(Osy
602 + epsilon)", i.e a combination of state and input, possibly empty to an
603 output symbol, or nothing.
604 For the graph representation this means that edges are additional
606 labeled with the output symbol to write when this edge is traversed
607 while matching input. Note that for an application "writing an output
608 symbol" can also be "executing some code".
609 Transducers are not handled by this package. They will get their own
611 package in the future.
612
614 This document, and the package it describes, will undoubtedly contain
615 bugs and other problems. Please report such in the category grammar_fa
616 of the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist]. Please
617 also report any ideas for enhancements you may have for either package
618 and/or documentation.
619 When proposing code changes, please provide unified diffs, i.e the out‐
621 put of diff -u.
622 Note further that attachments are strongly preferred over inlined
624 patches. Attachments can be made by going to the Edit form of the
625 ticket immediately after its creation, and then using the left-most
626 button in the secondary navigation bar.
627
629 automaton, finite automaton, grammar, parsing, regular expression, reg‐
630 ular grammar, regular languages, state, transducer
631
633 Grammars and finite automata
634
636 Copyright (c) 2004-2009 Andreas Kupries <andreas_kupries@users.sourceforge.net>
637tcllib 0.4 grammar::fa(n)