Daniel Pitts schrieb:

for me important would be to say that java's regexp seem not to be
equivalent to regexp in science (which have the same power as DFA or NFA
or epsilon-FA)

javas regexp allow you to backreference something you mached earlier
which might make them as powerful as a ContexFree-grammar/PDA (may be I
don't know, just a guess)

so it seems for me currently not proven that you can't do this parens
matching...
but this seems to be rather scientific intrest...there are better ways
to do it...

   I was thinking about these comments a bit more, and I realized I don't
really understand your notation. In particular, I have no idea how to read
your DA. What you call an NDA looks like a DA to me. That is,

(s)->a
   / \
  b   c
   \ /
    d->(e)

looks like a *deterministic* finite automaton, in that there's only ever at
most 1 possible transition you can take given the next input token and the
current state. To make it an NDA, you'd probably need something like:

(s)->a
   /|\
  / | \
 b  b  c
 |  |  |
 h  i  j
  \ | /
   \|/
    d->(e)

(which implements the regexp: "a(bh|bi|cj)d")

where if you're at the top state, and you see a b, you don't know whether to
take the left one or the middle one.

   But even then, I think (but cannot recall precisely) that the way the
terms NFA and DFA were defined to me, every DFA is considered to also be an
NFA (and so perhaps the N should stand for "not necessarily deterministic"
rather than "non-determistic"), but not every NFA is also a DFA.

   - Oliver

   I've never heard of these quantum FSAs, but they're probably not what
I was referring to in my quantum-computer-natively-running-NDA statement.

   Usually, when a classical computer tries to run an NDA, it either
converts it to an equivalent DFA (and thus risks getting an explosion of
states), or it keeps a set of all possible states the NDA could be in. For
example, if the classical computer thinks that the current possible set of
states that the NDA could be in is {s6}, and the NDA graph looks something
like...

           ,--a--->(s7)-->...
          /
...--->(s6)----a--->(s8)-->...
          \
           `--b--->(s9)-->...

   ... then upon encountering the token "a", the classical
single-processor computer will consume that token, and then update the set
of possible states to be {s7, s8}. Then it needs to look at the next
token, and compare that to the successors of s7, and iteratively, look at
the successors of s8. And you need to do this for each token in the input
string you're trying to accept. So the overall running time is something
like O(n*l), where n is the number of states, and l is the length of the
input. With multi-processors, you can start to do these computations in
parallel, but you're limited by the number of processors: a P-processor
classical computer could only analyze P states at a time, and in the worst
case NDA, you might not have any idea what state you're in at all, and so
you'd need as many processors as there are nodes the graph. P is constant
with respect to the problem size, and so the running time is still
O(n*l/P) == O(n*l).

   Quantum physics is nowhere near my expertise, but my understanding is
that with a quantum computer, there's some sort of natural fit between
"having a set of possible states the NDA could be in" and "have a set of
possible states a qubit could be in". You would just go through each token
of the input, transition by transition, until you reach the end, and then
you "observe" the qubit, revealing finally what state you ended up in (and
whether or not it is an accepting state). The running time becomes O(l),
directly proportional to the size of the input string, and unaffected by
the size of the graph.

   - Oliver

I don't think that does what you intend.  For instance, if it sees input string
")" then it'll end up in states {A,B}.  The ')' will take it from the start
state, A, to state A, and also (non-deterministically) to state B.  Since A is
accepting that means it will accept the input ")" -- which is rather noticeably
not a string of balanced, properly nested, brackets ;-)

It is equivalent to a DFA with two states, I'll call 'em S0 and S1.
S0 is the start state and is accepting.
There are four transitions as follows (I hope the notation is self-evident):
   S0 -- ) --> S0
   S0 -- ( --> S1
   S1 -- ( --> S1
   S1 -- ) --> S0

That DFA was generated and minimised mechanically, btw.  It is always possible
to transform an NFA into an equivalent DFA, and what's more it can be done by a
fairly simple algorithm -- no human insight required ;-)   The key point is
that, since the  NFA has -- by definition -- a finite set of states, the set of
/sets/ of states is also finite.  And by constructing a DFA with a state
corresponding to each (non-empty) set of NFA states, you can translate the NFA
into (typically rather bigger) DFA.  If you'd like more details then you could
start with the Wikipeadia article:
   http://en.wikipedia.org/wiki/Powerset_construction
(I haven't read it, so I don't know how clear, or even correct, it is, but it
does have convincing-looking pictures ;-)   Or try Google:
   nfa dfa construction

The algorithm yields a 3-state FSA with 6 transitions, and then minimising that
produces the above.

   -- chris

It accepts any string whose last character is ")", regardless of whether
the parentheses are balanced or not. There is an edge for ")" leading to
the accepting state A from both itself and B.

Each rung on the ladder can be represented by a set of states of the
NDFSA, and the next set of states depends only on the current set of
states and the input.

Patricia