Conference rusure::math

There is something seriously wrong with your assumptions.  Regular expression
recognition is equivalent in power to finite state machines.

							-- Jerry

I don't understand the first response.  How does the equivalence (in
power) of regular expressions to finite state machines invalidate the
assumptions in the problem statement? 
I also don't see how the response even addresses the original problem.
    	-john

re: .-1

Quoted from the base note:

	Anyone who is familiar with the Jackson design methodology will know
	that it is equivalent to regular expressions....  Because the\
	methodology is equivalent to regular expressions,\ the structure clash
	and backtracking problems are situations which \require more "memory"
	than a finite state machine can provide\....

	Given two regular expressions, R1 and R2, how do you determine whether
	or not you can build a finite state machine (with output) that will
	accept elements in R1 and output elements in R2?

In re-reading the final question while entering this note, I realized that I
hadn't read it closely enough the first time through.  It's not at all clear
what is required:  It is trivial to build an FSM that accepts elements in R1
and outputs some (fixed) element in R2.  Presumably, that's not what is
wanted; rather, there is some sort of translation that's supposed to be at
work, and you want some particular element of R2 for the given element of
R1.  How are you specifying the translation?  That's the crux of the prob-
lem here.
							-- Jerry

yes, I agree, the problem was not well stated due to my lack of understanding.
You are correct that it is the particular translation required which 
causes the problem.  The Jackson design methodology consists of some
design components (elementary components (atomic), sequence, iteration,
and selection) and a "basic three-step method".  The "translation" required
by certain kinds of problems cannot be accomplished using only the basic
method.  Essentially, a more formal explanation of this was required.
J.W. Hughes presented such an explanation in the paper "A Formalization 
and Explication of the Michael Jackson Method of Program Design", 
Software - Practice and Experience, VOL. 9, pp. 191-202, 1979.
He gives a list of rules which can be used to determine if an input
structure and an output structure "correspond" in such a way that the
program structure (design)  can be built using the basic method.
He then goes on to say that the set of "machines" which correspond
to problems solvable using the Jackson method are General Sequential
Machines (g.s.m. from Ginsberg), so every problem solvable with the
Jackson method is g.s.m. computable.  The problems which are not 
solvable by the Jackson method are show to violate one of the four
properties of g.s.m.s.  

thanks for trying,

. . .

Ellen