1grammar::fa::op(n) Finite automaton operations and usage grammar::fa::op(n)
2______________________________________________________________________________
6
8 grammar::fa::op - Operations on finite automatons
9
11 package require Tcl 8.4
12 package require snit
14 package require struct::list
16 package require struct::set
18 package require grammar::fa::op ?0.2?
20 ::grammar::fa::op::constructor cmd
22 ::grammar::fa::op::reverse fa
24 ::grammar::fa::op::complete fa ?sink?
26 ::grammar::fa::op::remove_eps fa
28 ::grammar::fa::op::trim fa ?what?
30 ::grammar::fa::op::determinize fa ?mapvar?
32 ::grammar::fa::op::minimize fa ?mapvar?
34 ::grammar::fa::op::complement fa
36 ::grammar::fa::op::kleene fa
38 ::grammar::fa::op::optional fa
40 ::grammar::fa::op::union fa fb ?mapvar?
42 ::grammar::fa::op::intersect fa fb ?mapvar?
44 ::grammar::fa::op::difference fa fb ?mapvar?
46 ::grammar::fa::op::concatenate fa fb ?mapvar?
48 ::grammar::fa::op::fromRegex fa regex ?over?
50_________________________________________________________________
52
54 This package provides a number of complex operations on finite automa‐
55 tons (Short: FA), as provided by the package grammar::fa. The package
56 does not provide the ability to create and/or manipulate such FAs, nor
57 the ability to execute a FA for a stream of symbols. Use the packages
58 grammar::fa and grammar::fa::interpreter for that. Another package
59 related to this is grammar::fa::compiler which turns a FA into an
60 executor class which has the definition of the FA hardwired into it.
61 For more information about what a finite automaton is see section
63 FINITE AUTOMATONS in package grammar::fa.
64
66 The package exports the API described here. All commands modify their
67 first argument. I.e. whatever FA they compute is stored back into it.
68 Some of the operations will construct an automaton whose states are all
69 new, but related to the states in the source automaton(s). These opera‐
70 tions take variable names as optional arguments where they will store
71 mappings which describe the relationship(s). The operations can be
72 loosely partitioned into structural and language operations. The latter
73 are defined in terms of the language the automaton(s) accept, whereas
74 the former are defined in terms of the structural properties of the
75 involved automaton(s). Some operations are both. Structure operations
76 ::grammar::fa::op::constructor cmd
78 This command has to be called by the user of the package before
79 any other operations is performed, to establish a command which
80 can be used to construct a FA container object. If this is not
81 done several operations will fail as they are unable to con‐
82 struct internal and transient containers to hold state and/or
83 partial results.
84 Any container class using this package for complex operations
86 should set its own class command as the constructor. See package
87 grammar::fa for an example.
88 ::grammar::fa::op::reverse fa
90 Reverses the fa. This is done by reversing the direction of all
91 transitions and swapping the sets of start and final states. The
92 language of fa changes unpredictably.
93 ::grammar::fa::op::complete fa ?sink?
95 Completes the fa complete, but nothing is done if the fa is
96 already complete. This implies that only the first in a series
97 of multiple consecutive complete operations on fa will perform
98 anything. The remainder will be null operations.
99 The language of fa is unchanged by this operation.
101 This is done by adding a single new state, the sink, and transi‐
103 tions from all other states to that sink for all symbols they
104 have no transitions for. The sink itself is made complete by
105 adding loop transitions for all symbols.
106 Note: When a FA has epsilon-transitions transitions over a sym‐
108 bol for a state S can be indirect, i.e. not attached directly to
109 S, but to a state in the epsilon-closure of S. The symbols for
110 such indirect transitions count when computing completeness of a
111 state. In other words, these indirectly reached symbols are not
112 missing.
113 The argument sink provides the name for the new state and most
115 not be present in the fa if specified. If the name is not speci‐
116 fied the command will name the state "sinkn", where n is set so
117 that there are no collisions with existing states.
118 Note that the sink state is not useful by definition. In other
120 words, while the FA becomes complete, it is also not useful in
121 the strict sense as it has a state from which no final state can
122 be reached.
123 ::grammar::fa::op::remove_eps fa
125 Removes all epsilon-transitions from the fa in such a manner the
126 the language of fa is unchanged. However nothing is done if the
127 fa is already epsilon-free. This implies that only the first in
128 a series of multiple consecutive complete operations on fa will
129 perform anything. The remainder will be null operations.
130 Note: This operation may cause states to become unreachable or
132 not useful. These states are not removed by this operation. Use
133 ::grammar::fa::op::trim for that instead.
134 ::grammar::fa::op::trim fa ?what?
136 Removes unwanted baggage from fa. The legal values for what are
137 listed below. The command defaults to !reachable|!useful if no
138 specific argument was given.
139 !reachable
141 Removes all states which are not reachable from a start
142 state.
143 !useful
145 Removes all states which are unable to reach a final
146 state.
147 !reachable&!useful
149 !(reachable|useful)
151 Removes all states which are not reachable from a start
152 state and are unable to reach a final state.
153 !reachable|!useful
155 !(reachable&useful)
157 Removes all states which are not reachable from a start
158 state or are unable to reach a final state.
159 ::grammar::fa::op::determinize fa ?mapvar?
162 Makes the fa deterministic without changing the language
163 accepted by the fa. However nothing is done if the fa is already
164 deterministic. This implies that only the first in a series of
165 multiple consecutive complete operations on fa will perform any‐
166 thing. The remainder will be null operations.
167 The command will store a dictionary describing the relationship
169 between the new states of the resulting dfa and the states of
170 the input nfa in mapvar, if it has been specified. Keys of the
171 dictionary are the handles for the states of the resulting dfa,
172 values are sets of states from the input nfa.
173 Note: An empty dictionary signals that the command was able to
175 make the fa deterministic without performing a full subset con‐
176 struction, just by removing states and shuffling transitions
177 around (As part of making the FA epsilon-free).
178 Note: The algorithm fails to make the FA deterministic in the
180 technical sense if the FA has no start state(s), because deter‐
181 minism requires the FA to have exactly one start states. In
182 that situation we make a best effort; and the missing start
183 state will be the only condition preventing the generated result
184 from being deterministic. It should also be noted that in this
185 case the possibilities for trimming states from the FA are also
186 severely reduced as we cannot declare states unreachable.
187 ::grammar::fa::op::minimize fa ?mapvar?
189 Creates a FA which accepts the same language as fa, but has a
190 minimal number of states. Uses Brzozowski's method to accomplish
191 this.
192 The command will store a dictionary describing the relationship
194 between the new states of the resulting minimal fa and the
195 states of the input fa in mapvar, if it has been specified. Keys
196 of the dictionary are the handles for the states of the result‐
197 ing minimal fa, values are sets of states from the input fa.
198 Note: An empty dictionary signals that the command was able to
200 minimize the fa without having to compute new states. This
201 should happen if and only if the input FA was already minimal.
202 Note: If the algorithm has no start or final states to work with
204 then the result might be technically minimal, but have a very
205 unexpected structure. It should also be noted that in this case
206 the possibilities for trimming states from the FA are also se‐
207 verely reduced as we cannot declare states unreachable. Lan‐
208 guage operations All operations in this section require that all
209 input FAs have at least one start and at least one final state.
210 Otherwise the language of the FAs will not be defined, making
211 the operation senseless (as it operates on the languages of the
212 FAs in a defined manner).
213 ::grammar::fa::op::complement fa
215 Complements fa. This is possible if and only if fa is complete
216 and deterministic. The resulting FA accepts the complementary
217 language of fa. In other words, all inputs not accepted by the
218 input are accepted by the result, and vice versa.
219 The result will have all states and transitions of the input,
221 and different final states.
222 ::grammar::fa::op::kleene fa
224 Applies Kleene's closure to fa. The resulting FA accepts all
225 strings S for which we can find a natural number n (0 inclusive)
226 and strings A1 ... An in the language of fa such that S is the
227 concatenation of A1 ... An. In other words, the language of the
228 result is the infinite union over finite length concatenations
229 over the language of fa.
230 The result will have all states and transitions of the input,
232 and new start and final states.
233 ::grammar::fa::op::optional fa
235 Makes the fa optional. In other words it computes the FA which
236 accepts the language of fa and the empty the word (epsilon) as
237 well.
238 The result will have all states and transitions of the input,
240 and new start and final states.
241 ::grammar::fa::op::union fa fb ?mapvar?
243 Combines the FAs fa and fb such that the resulting FA accepts
244 the union of the languages of the two FAs.
245 The result will have all states and transitions of the two input
247 FAs, and new start and final states. All states of fb which
248 exist in fa as well will be renamed, and the mapvar will contain
249 a mapping from the old states of fb to the new ones, if present.
250 It should be noted that the result will be non-deterministic,
252 even if the inputs are deterministic.
253 ::grammar::fa::op::intersect fa fb ?mapvar?
255 Combines the FAs fa and fb such that the resulting FA accepts
256 the intersection of the languages of the two FAs. In other
257 words, the result will accept a word if and only if the word is
258 accepted by both fa and fb. The result will be useful, but not
259 necessarily deterministic or minimal.
260 The command will store a dictionary describing the relationship
262 between the new states of the resulting fa and the pairs of
263 states of the input FAs in mapvar, if it has been specified.
264 Keys of the dictionary are the handles for the states of the
265 resulting fa, values are pairs of states from the input FAs.
266 Pairs are represented by lists. The first element in each pair
267 will be a state in fa, the second element will be drawn from fb.
268 ::grammar::fa::op::difference fa fb ?mapvar?
270 Combines the FAs fa and fb such that the resulting FA accepts
271 the difference of the languages of the two FAs. In other words,
272 the result will accept a word if and only if the word is
273 accepted by fa, but not by fb. This can also be expressed as the
274 intersection of fa with the complement of fb. The result will be
275 useful, but not necessarily deterministic or minimal.
276 The command will store a dictionary describing the relationship
278 between the new states of the resulting fa and the pairs of
279 states of the input FAs in mapvar, if it has been specified.
280 Keys of the dictionary are the handles for the states of the
281 resulting fa, values are pairs of states from the input FAs.
282 Pairs are represented by lists. The first element in each pair
283 will be a state in fa, the second element will be drawn from fb.
284 ::grammar::fa::op::concatenate fa fb ?mapvar?
286 Combines the FAs fa and fb such that the resulting FA accepts
287 the cross-product of the languages of the two FAs. I.e. a word W
288 will be accepted by the result if there are two words A and B
289 accepted by fa, and fb resp. and W is the concatenation of A and
290 B.
291 The result FA will be non-deterministic.
293 ::grammar::fa::op::fromRegex fa regex ?over?
295 Generates a non-deterministic FA which accepts the same language
296 as the regular expression regex. If the over is specified it is
297 treated as the set of symbols the regular expression and the au‐
298 tomaton are defined over. The command will compute the set from
299 the "S" constructors in regex when over was not specified. This
300 set is important if and only if the complement operator "!" is
301 used in regex as the complementary language of an FA is quite
302 different for different sets of symbols.
303 The regular expression is represented by a nested list, which
305 forms a syntax tree. The following structures are legal:
306 {S x} Atomic regular expression. Everything else is constructed
308 from these. Accepts the Symbol "x".
309 {. A1 A2 ...}
311 Concatenation operator. Accepts the concatenation of the
312 regular expressions A1, A2, etc.
313 {| A1 A2 ...}
315 Choice operator, also called "Alternative". Accepts all
316 input accepted by at least one of the regular expressions
317 A1, A2, etc. In other words, the union of A1, A2.
318 {& A1 A2 ...}
320 Intersection operator, logical and. Accepts all input
321 accepted which is accepted by all of the regular expres‐
322 sions A1, A2, etc. In other words, the intersection of
323 A1, A2.
324 {? A} Optionality operator. Accepts the empty word and anything
326 from the regular expression A.
327 {* A} Kleene closure. Accepts the empty word and any finite
329 concatenation of words accepted by the regular expression
330 A.
331 {+ A} Positive Kleene closure. Accepts any finite concatenation
333 of words accepted by the regular expression A, but not
334 the empty word.
335 {! A} Complement operator. Accepts any word not accepted by the
337 regular expression A. Note that the complement depends on
338 the set of symbol the result should run over. See the
339 discussion of the argument over before.
340
343 automaton, finite automaton, grammar, parsing, regular expression, reg‐
344 ular grammar, regular languages, state, transducer
345
347 Copyright (c) 2004 Andreas Kupries <andreas_kupries@users.sourceforge.net>
348grammar_fa 0.2 grammar::fa::op(n)