Parens Matching

[Daniel Pitts]

I think Daniel's notation is non-standard, but it does make seem to make sense.
What he's doing is removing the states themselves from the picture, leaving
only the trails of input words that have been recognised.

It is indeed non-standard. I was trying to represent transitions more
than states, and was trying to do so concisely.

So in:

Whereas "a[bc]d" produces the NDA
(s)->a
/ \
b c
\ /
d->(e)

the first 'a' is not a state label, but marks the fact that we have accepted an
'a'. The actual state we are in has no name (in this notation) but is sort of
hidden "just after" the label 'a'. From that state we can transition by
accepting 'b' to an anonymous state hidden behind the label 'b', or can
transition by accepting 'c' to the anonymous state hidden behind the 'c' label.
And from either of those states we can accept 'd' to go to the corresponding
state, and since that is a final state, we have matched the input. And the NFA
does indeed recognise a(b|c)d.

I don't think the notation covers all possible cases, for all it is nice and
clear for the cases it /does/ cover. The problems comes when one state has two
or more incoming edges with different labels (including epsilon transitions):

(S0)---x---> (S1)
| |
a y
| |
v |
(S2)---b--->[S3]

(I hope my ASCII art is legible). S0 is the start state, from which we can
transition via 'x' to S1, or via 'a' to S2. From S1 and S2 we can transition
via 'b' or 'y' (respectively) to S3, the accepting state. Thus it recognises
(ab|xy). I don't think that can be represented in Daniel's notation without
changing the definition of the NFA itself.

I don't know whether every regexp can be represented as /some/ NFA in Daniel's
notation. I haven't been able to think of a counter example yet, although the
NFA is sometimes more awkward than one which can be written in the classic
diagram format.

I wasn't trying to create an all-purpose notation, I doubt it works
for all regexp, but it might.

It depends on how you see it. Every DFA corresponds trivially to an NFA with
the same structure, so in that sense the DFAs are a subset of the NFAs. But
the formal definition of a DFA is different from that of a NFA, since it has a
/single/' state at any one time rather than a set of states. And of course
type Set<State> is not assignable to, or from, type State.

In Java, that may be true, but in implementing a NFA-to-DFA converter,
you may choose to create a class StateSet implements State, since
every State in the DFA results from a set of states in the NDA.

Daniel.

 

[Chris Uppal]

The interests in NDAs is that they take up less "code" to represent
(recall that a K state NDA translates into a 2^K state DA), *and* (and
here's the part that makes them interesting to study nowadays) a quantum
computer can run NDAs "natively", whereas a classical computer would have
to emulate the NDA by converting it (either implicitly or explicitly)
into a DA, and gain that 2^K performance penalty factor.

BTW: As far as I can tell, the quantum theorists are claiming that a quantum
FSA can recognise more than just the regular languages.

(Personally, I think that if that claim is true, and if it has physical
meaning, then all it means is that the things claimed to be quantum analogues
of FSAs are not actually analogous.)

-- chris

 

[Oliver Wong]

BTW: As far as I can tell, the quantum theorists are claiming that a
quantum
FSA can recognise more than just the regular languages.

(Personally, I think that if that claim is true, and if it has physical
meaning, then all it means is that the things claimed to be quantum
analogues
of FSAs are not actually analogous.)

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