Reducing FSAs with empty trans. with arb. output

Synopsis for those too lazy to read:
      I want to know how to remove lambda loops in
      Finite State Automata when the lambda (empty input)
      transitions may have arbitrary outputs.


I am currently writing routines to mechanically transcribe
from regular grammars to finite state machines. As always,
i have stumbled upon what I feel is a difficult problem.


The problem comes in trying to remove empty transitions from
my finite state machine- in particular the removal of lambda
loops is problematic.


The probelm started with me not wishing to make my routines
specific to a boolean output. (this is unclear: i'll expand):


I have made a machine with transition based output- the
machine has a number of states, and on input the current
state switches from one state to another, producing output
as it jumps.


+---------------------------------------------------------------+
|
| (in: a, out: False)
| | |
| | |
| | |
| | |
| --> (state 1) <-------+
| |
| +----------(in: b, out: True) ------> (state b)
|
|
| ASCII art to demostrate- this has false output whilst
| input is a, then true on input b
| this matches regular expression (a* b)
+---------------------------------------------------------------


Now we can also have transitions on empty input, these may also have
output. However, we wish to remove these transitions- they are
nondeterministic. this is done by combining them: more ascii art


+------------------------------------------------------------
|
| --> (s1) --(in: empty, out: a)----> (s2)
| |
| |
| (in: A, out: b)
| |
| \|/
| (s3)
|
+-----------------------------------------------------------
becomes
+------------------------------------------------------------
|
| --> (s1) (s2)
| | |
| | |
| | (in: A, out: b)
| | |
| | \|/
| +-(in A, out ab)------------->(s3)
|
+-----------------------------------------------------------


My question to you is this :


If the lambdas are in a loop, how is the input handled: we
can have potentially infinte looping, and therefore infinte
output. I have included a clip from a paper I am writing.
For space reasons, I am not going to define my terms, these
may become clear via context.


regards
  Johan


clipping starts here:
A more difficult problem is that of loops; two or more lambda
transitions may form a loop. If these transitions have outputs,
a potentially infinite number of transitions may be needed to
replace them (footnote: The machine could conceivable cycle
endlessly between the states, generating output.). I must admit
that I have been unable to find an acceptable solution to this.
We have two approaches we may take, both with fatal flaws:


1) Ignore all but the last output. This is acceptable for
recognisers;
in them we only care about the results of the last transition. However,
this is not genrally true- if we wish to at anytime concatenate several
machines, so that he output of one becomes the input of the next, this
approach will not work, as we will be losing some outputs before they
are (should be) generated.


2) Accept the problem as difficult. Recognise when a loop is
unsolvable, and ask the user to rewrite itby hand. This is
obviously not what we intended when we set out to write mechanical
transcription routines. However, the parser which converts from a
regular expression to a regual grammar will not introduce any such
loops (footnote: JOHAN prove this). For our purposes, this problem
(bug) should not crop up. All the same, Having a routine with a
glaring bug is inacceptable.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.