Re: Parens Matching

Michael wrote:
> On Feb 15, 7:34 pm, "Ken Kast" <k...@NOSPAM-kenkast.com> wrote:
>> Does anyone have a regular expression pattern that would include a test for
>> balanced parens of arbitrary nestedness?
>
> No. No one does.
>
> There's a well known proof in Computer Science theory that it is not
> possible to create a regular expression for balanced parentheses.
>
> Look up "the pumping lemma" for details.

That thang always made me think of either pumping lemons or pumping
lemmings.

The matched parenthesis problem can be done with a non-deterministic
state machine, but not with a deterministic one.... hence no regular
expression can do it.

On Feb 16, 5:26 pm, Alex Hunsley <red...@bluebottle.com> wrote:
> Michael wrote:
> > On Feb 15, 7:34 pm, "Ken Kast" <k...@NOSPAM-kenkast.com> wrote:
> >> Does anyone have a regular expression pattern that would include a test for
> >> balanced parens of arbitrary nestedness?
>
> > No. No one does.
>
> > There's a well known proof in Computer Science theory that it is not
> > possible to create a regular expression for balanced parentheses.
>
> > Look up "the pumping lemma" for details.
>
> That thang always made me think of either pumping lemons or pumping
> lemmings.
>
> The matched parenthesis problem can be done with a non-deterministic
> state machine, but not with a deterministic one.... hence no regular
> expression can do it.

Hmm, I don't think your definition is correct.
Regex isn't always implementedwith a DSM, it might use NDA, which
still doesn't solve it.

In either case, the following is a deterministic state machine solves
the problem.

private static boolean isBalancedCount(String string) {
int parens = 0;
for (char c : string.toCharArray()) {
if (c == '(') {
++parens;
}
if (c == ')' && --parens < 0) {
return false;
}
}
return parens == 0;
}

Daniel Pitts wrote:
> On Feb 16, 5:26 pm, Alex Hunsley <red...@bluebottle.com> wrote:
>> Michael wrote:
>>> On Feb 15, 7:34 pm, "Ken Kast" <k...@NOSPAM-kenkast.com> wrote:
>>>> Does anyone have a regular expression pattern that would include a test for
>>>> balanced parens of arbitrary nestedness?
>>> No. No one does.
>>> There's a well known proof in Computer Science theory that it is not
>>> possible to create a regular expression for balanced parentheses.
>>> Look up "the pumping lemma" for details.
>> That thang always made me think of either pumping lemons or pumping
>> lemmings.
>>
>> The matched parenthesis problem can be done with a non-deterministic
>> state machine, but not with a deterministic one.... hence no regular
>> expression can do it.
>
> Hmm, I don't think your definition is correct.
> Regex isn't always implementedwith a DSM, it might use NDA, which
> still doesn't solve it.

What do you mean by NDA? Non-deterministic automaton?

>
> In either case, the following is a deterministic state machine solves
> the problem.
>
> private static boolean isBalancedCount(String string) {
> int parens = 0;
> for (char c : string.toCharArray()) {
> if (c == '(') {
> ++parens;
> }
> if (c == ')' && --parens < 0) {
> return false;
> }
> }
> return parens == 0;
> }

Nope, it doesn't solve the problem. The int type in Java has finite
capacity - see Integer.MAX_VALUE - so more accurately this a finite
deterministic state machine. I'm actually trying to remember if
'deterministic state machine' usually implies the 'finite' part in
common usage. A look at wikipedia seems to suggest that, but I wasn't
looking at it for long...

So, anyway, I can think of an input that causes the above code to fail -
and hence problem not solved.

To give a simplified example of this, suppose we have a Java where
Integer.MAX_VALUE = 1, and .MIN_VALUE = -2. So an int can have 4
distinct values for int. Assuming this, would would your code save about
the following inputs?

(((( - this would be a false positive
(((((((( - another false positive
((())) - this would be a false negative


Similarly, your code above in the world of real Java would give a false
positive for the input:

'(' * [(Integer.MAX_VALUE - Integer.MIN_VALUE + 1) * n]

where n is any positive integer.

Basically, true parens matching is scuppered, because of the need for
infinite memory!

lex

Alex Hunsley wrote:

> The matched parenthesis problem can be done with a non-deterministic
> state machine, but not with a deterministic one.... hence no regular
> expression can do it.

I would understand "non-deterministic state machine" to mean the
non-deterministic variant of finite state automaton). And the deterministic
and non-deterministic versions of FSAs are equivalent in power. Do you use the
term to mean something other form of automaton ?

-- chris

On Feb 17, 4:16 am, Alex Hunsley <red...@bluebottle.com> wrote:
> Daniel Pitts wrote:
> > On Feb 16, 5:26 pm, Alex Hunsley <red...@bluebottle.com> wrote:
> >> Michael wrote:
> >>> On Feb 15, 7:34 pm, "Ken Kast" <k...@NOSPAM-kenkast.com> wrote:
> >>>> Does anyone have a regular expression pattern that would include a test for
> >>>> balanced parens of arbitrary nestedness?
> >>> No. No one does.
> >>> There's a well known proof in Computer Science theory that it is not
> >>> possible to create a regular expression for balanced parentheses.
> >>> Look up "the pumping lemma" for details.
> >> That thang always made me think of either pumping lemons or pumping
> >> lemmings.
>
> >> The matched parenthesis problem can be done with a non-deterministic
> >> state machine, but not with a deterministic one.... hence no regular
> >> expression can do it.
>
> > Hmm, I don't think your definition is correct.
> > Regex isn't always implementedwith a DSM, it might use NDA, which
> > still doesn't solve it.
>
> What do you mean by NDA? Non-deterministic automaton?
>
>
>
>
>
> > In either case, the following is a deterministic state machine solves
> > the problem.
>
> > private static boolean isBalancedCount(String string) {
> > int parens = 0;
> > for (char c : string.toCharArray()) {
> > if (c == '(') {
> > ++parens;
> > }
> > if (c == ')' && --parens < 0) {
> > return false;
> > }
> > }
> > return parens == 0;
> > }
>
> Nope, it doesn't solve the problem. The int type in Java has finite
> capacity - see Integer.MAX_VALUE - so more accurately this a finite
> deterministic state machine. I'm actually trying to remember if
> 'deterministic state machine' usually implies the 'finite' part in
> common usage. A look at wikipedia seems to suggest that, but I wasn't
> looking at it for long...
>
> So, anyway, I can think of an input that causes the above code to fail -
> and hence problem not solved.
>
> To give a simplified example of this, suppose we have a Java where
> Integer.MAX_VALUE = 1, and .MIN_VALUE = -2. So an int can have 4
> distinct values for int. Assuming this, would would your code save about
> the following inputs?
>
> (((( - this would be a false positive
> (((((((( - another false positive
> ((())) - this would be a false negative
>
> Similarly, your code above in the world of real Java would give a false
> positive for the input:
>
> '(' * [(Integer.MAX_VALUE - Integer.MIN_VALUE + 1) * n]
>
> where n is any positive integer.
>
> Basically, true parens matching is scuppered, because of the need for
> infinite memory!
>
> lex

(((( and (((((((( both give the correct output.
((())) also results in the correct output. Hmm, are you sure you
analyzed my algorithm correctly?

As for the case of:
'(' * [(Integer.MAX_VALUE - Integer.MIN_VALUE + 1) * n]

You're talking about at least a 4 gigabyte string. As a mater of
practicality, I find that type of input to be unreasonable, but it
would be simple enough to change the code to hand off to a different
algorithm:

private static boolean isBalancedCount(String string) {
int parens = 0;
for (char c : string.toCharArray()) {
if (c == '(' && parens++ == Integer.MAX_INT) {
// We can't handle the trueth, but isBalancedRe can!
return isBalancedRe(string);
}
if (c == ')' && --parens < 0) {
return false;
}
}
return parens == 0;
}

Daniel Pitts wrote:
> On Feb 17, 4:16 am, Alex Hunsley <red...@bluebottle.com> wrote:
>> To give a simplified example of this, suppose we have a Java where
>> Integer.MAX_VALUE = 1, and .MIN_VALUE = -2. So an int can have 4
>> distinct values for int. Assuming this, would would your code save about
>> the following inputs?
>>
>> (((( - this would be a false positive
>> (((((((( - another false positive
>> ((())) - this would be a false negative
>>
>> Similarly, your code above in the world of real Java would give a false
>> positive for the input:
>>
>> '(' * [(Integer.MAX_VALUE - Integer.MIN_VALUE + 1) * n]
>>
>> where n is any positive integer.
>>
>> Basically, true parens matching is scuppered, because of the need for
>> infinite memory!
>>
>> lex
>
> (((( and (((((((( both give the correct output.
> ((())) also results in the correct output. Hmm, are you sure you
> analyzed my algorithm correctly?

I wasn't talking about your code running under normal Java, I was
talking about a pretend one with very small Integer.MAX_VALUE etc. To
quote myself: "To give a simplified example of this, suppose we have a
Java where ... [stuff] ... assuming this, what would your code [say]
about the following inputs?" I was making a simplification to make a
more accessible toy example where it was easy to play with the cases
where it would produce the wrong answers for 'extreme' cases.

> As for the case of:
> '(' * [(Integer.MAX_VALUE - Integer.MIN_VALUE + 1) * n]
>
> You're talking about at least a 4 gigabyte string. As a mater of
> practicality, I find that type of input to be unreasonable, but it
> would be simple enough to change the code to hand off to a different
> algorithm:

I think we're coming back to the issue mentioned before about theory
versus practicality: I do know that your code works for all practical
purposes - it's correct for all practical purposes - as opposed to the
computer science theoretic sense in which bracket matching can't be done
(by a regular expression or by a FSA or by a finite computer).

I'm just being too theoretic for my own good, is all....

lex

Chris Uppal wrote:
> Alex Hunsley wrote:
>
>> The matched parenthesis problem can be done with a non-deterministic
>> state machine, but not with a deterministic one.... hence no regular
>> expression can do it.
>
> I would understand "non-deterministic state machine" to mean the
> non-deterministic variant of finite state automaton). And the deterministic
> and non-deterministic versions of FSAs are equivalent in power.

Are you sure about that? As far as I can recall, a non-deterministic FSA
(as that is what I am meaning) can solve the bracket matching problem,
but a deterministic one can't. Put it this way - how would you design a
deterministic FSA that did bracket matching on arbitrary length input?
You can't, if it is going to remain finite... And it's easy enough to do
with a non-deterministic FSA.

Is it that *some* non-deterministic FSA can be 'unfolded' into
deterministic ones, but not all, perhaps?

lex

> Do you use the
> term to mean something other form of automaton ?

No, FSA is right, that's basically what I'm thinking of...

Alex Hunsley wrote:
> Chris Uppal wrote:
>> Alex Hunsley wrote:
>>
>>> The matched parenthesis problem can be done with a non-deterministic
>>> state machine, but not with a deterministic one.... hence no regular
>>> expression can do it.
>> I would understand "non-deterministic state machine" to mean the
>> non-deterministic variant of finite state automaton). And the deterministic
>> and non-deterministic versions of FSAs are equivalent in power.
>
> Are you sure about that? As far as I can recall, a non-deterministic FSA
> (as that is what I am meaning) can solve the bracket matching problem,
> but a deterministic one can't. Put it this way - how would you design a
> deterministic FSA that did bracket matching on arbitrary length input?
> You can't, if it is going to remain finite... And it's easy enough to do
> with a non-deterministic FSA.

How do you do it with a non-deterministic FSA?

>
> Is it that *some* non-deterministic FSA can be 'unfolded' into
> deterministic ones, but not all, perhaps?

No, ANY non-deterministic FSA can be unfolded into a deterministic one.

The simple, brute force, approach is to create a DFSA whose states are
the sets of states of the NDFSA. It has a transition from x to y on
input symbol s if, and only if, y is the set of possible states of the
NDFSA after input s when in some state in x.

The DFSA's start state is the set of start states of the NDFSA. Its
accept states are those states that contain at least one of the NDFSA's
accept states.

The DFSA tracks the set of states the NDFSA could reach, from any start
state, given the input so far.

Patricia

Patricia Shanahan wrote:
> Alex Hunsley wrote:
>> Chris Uppal wrote:
>>> Alex Hunsley wrote:
>>>
>>>> The matched parenthesis problem can be done with a non-deterministic
>>>> state machine, but not with a deterministic one.... hence no regular
>>>> expression can do it.
>>> I would understand "non-deterministic state machine" to mean the
>>> non-deterministic variant of finite state automaton). And the
>>> deterministic
>>> and non-deterministic versions of FSAs are equivalent in power.
>>
>> Are you sure about that? As far as I can recall, a non-deterministic FSA
>> (as that is what I am meaning) can solve the bracket matching problem,
>> but a deterministic one can't. Put it this way - how would you design a
>> deterministic FSA that did bracket matching on arbitrary length input?
>> You can't, if it is going to remain finite... And it's easy enough to do
>> with a non-deterministic FSA.
>
> How do you do it with a non-deterministic FSA?

Here's one I just sketched. Does it look right?

http://farm1.static.flickr.com/136/3...66f451.jpg?v=0

But I can't see how this can be made into a DFSA because from what I
sketched for that you end up with a big 'ladder' of states that
stretches off to infinity (hence non finite).


>> Is it that *some* non-deterministic FSA can be 'unfolded' into
>> deterministic ones, but not all, perhaps?
>
> No, ANY non-deterministic FSA can be unfolded into a deterministic one.
>
> The simple, brute force, approach is to create a DFSA whose states are
> the sets of states of the NDFSA. It has a transition from x to y on
> input symbol s if, and only if, y is the set of possible states of the
> NDFSA after input s when in some state in x.
>
> The DFSA's start state is the set of start states of the NDFSA. Its
> accept states are those states that contain at least one of the NDFSA's
> accept states.
>
> The DFSA tracks the set of states the NDFSA could reach, from any start
> state, given the input so far.

Thanks for the reminder of all that!
lex

Alex Hunsley wrote:

> Here's one I just sketched. Does it look right?
>
> http://farm1.static.flickr.com/136/3...66f451.jpg?v=0

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 ;-)


> But I can't see how this can be made into a DFSA because from what I
> sketched for that you end up with a big 'ladder' of states that
> stretches off to infinity (hence non finite).

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

Alex Hunsley wrote:
> Patricia Shanahan wrote:
>> Alex Hunsley wrote:
>>> Chris Uppal wrote:
>>>> Alex Hunsley wrote:
>>>>
>>>>> The matched parenthesis problem can be done with a non-deterministic
>>>>> state machine, but not with a deterministic one.... hence no regular
>>>>> expression can do it.
>>>> I would understand "non-deterministic state machine" to mean the
>>>> non-deterministic variant of finite state automaton). And the
>>>> deterministic
>>>> and non-deterministic versions of FSAs are equivalent in power.
>>>
>>> Are you sure about that? As far as I can recall, a non-deterministic FSA
>>> (as that is what I am meaning) can solve the bracket matching problem,
>>> but a deterministic one can't. Put it this way - how would you design a
>>> deterministic FSA that did bracket matching on arbitrary length input?
>>> You can't, if it is going to remain finite... And it's easy enough to do
>>> with a non-deterministic FSA.
>>
>> How do you do it with a non-deterministic FSA?
>
> Here's one I just sketched. Does it look right?
>
> http://farm1.static.flickr.com/136/3...66f451.jpg?v=0

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.

> But I can't see how this can be made into a DFSA because from what I
> sketched for that you end up with a big 'ladder' of states that
> stretches off to infinity (hence non finite).

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

Patricia Shanahan schrieb:
> Alex Hunsley wrote:
>> Patricia Shanahan wrote:
>>> Alex Hunsley wrote:
>>>> Chris Uppal wrote:
>>>>> Alex Hunsley wrote:
>>>>>
>>>>>> The matched parenthesis problem can be done with a non-deterministic
>>>>>> state machine, but not with a deterministic one.... hence no regular
>>>>>> expression can do it.
>>>>> I would understand "non-deterministic state machine" to mean the
>>>>> non-deterministic variant of finite state automaton). And the
>>>>> deterministic
>>>>> and non-deterministic versions of FSAs are equivalent in power.
>>>>
>>>> Are you sure about that? As far as I can recall, a non-deterministic
>>>> FSA
>>>> (as that is what I am meaning) can solve the bracket matching problem,
>>>> but a deterministic one can't. Put it this way - how would you design a
>>>> deterministic FSA that did bracket matching on arbitrary length input?
>>>> You can't, if it is going to remain finite... And it's easy enough
>>>> to do
>>>> with a non-deterministic FSA.
>>>
>>> How do you do it with a non-deterministic FSA?
>>
>> Here's one I just sketched. Does it look right?
>>
>> http://farm1.static.flickr.com/136/3...66f451.jpg?v=0
>
> 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.
>
>> But I can't see how this can be made into a DFSA because from what I
>> sketched for that you end up with a big 'ladder' of states that
>> stretches off to infinity (hence non finite).
>
the power set of any finite set is finite!
http://en.wikipedia.org/wiki/Powerset_construction
basically the same for any automat or machine ... non deterministic and
deterministic allways have the same power ..
even on a touring machine ... non-deterministic may just be faster...

> 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

"Alex Hunsley" <redlex@bluebottle.com> wrote in message
news:mmCBh.342519$MO2.286238@fe3.news.blueyonder.c o.uk...
> Daniel Pitts wrote:
>> On Feb 16, 5:26 pm, Alex Hunsley <red...@bluebottle.com> wrote:
>>> The matched parenthesis problem can be done with a non-deterministic
>>> state machine, but not with a deterministic one.... hence no regular
>>> expression can do it.

I disagree, because a proof (by construction) exists which shows that
any non-deterministic state machine can be converted to a determinisitc
state machine. If the NDSM has K states, then DSM will have 2^K states. If
you allow for infinite NDSM, it only seems fair that you also allow for
infinite DSMs.

>>
>> Hmm, I don't think your definition is correct.
>> Regex isn't always implementedwith a DSM, it might use NDA, which
>> still doesn't solve it.
>
> What do you mean by NDA? Non-deterministic automaton?

Probably. I'll come back to this in a moment later in this post.

>
>>
>> In either case, the following is a deterministic state machine solves
>> the problem.
>>
>> private static boolean isBalancedCount(String string) {
>> int parens = 0;
>> for (char c : string.toCharArray()) {
>> if (c == '(') {
>> ++parens;
>> }
>> if (c == ')' && --parens < 0) {
>> return false;
>> }
>> }
>> return parens == 0;
>> }
>
> Nope, it doesn't solve the problem. The int type in Java has finite
> capacity - see Integer.MAX_VALUE - so more accurately this a finite
> deterministic state machine. I'm actually trying to remember if
> 'deterministic state machine' usually implies the 'finite' part in common
> usage. A look at wikipedia seems to suggest that, but I wasn't looking at
> it for long...

The usually, when someone talks about deterministic automatons and
non-deterministic automatons, they mean finite ones. So the usual
abbreviations are DFA and NDFA. We can, of course, talk about infinite
automatons, but there seems to be less literature on that topic (perhaps
because it's equivalent to, but more complex than, some other machine, e.g.
a push down stack machine or a Turing Machine or something, I don't know).

So if you're talking about finite DAs and Nodes, then they cannot solve
the "balance parentheses" problem. If you're talking about infinite ones,
then if a NDA can solve it, so can a DA. And if a NDA cannot solve it,
neither can a DA. The two are equivalent in power.

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.

- Oliver

On Feb 21, 9:21 am, "Oliver Wong" <o...@castortech.com> wrote:
> "Alex Hunsley" <red...@bluebottle.com> wrote in message
>
> news:mmCBh.342519$MO2.286238@fe3.news.blueyonder.c o.uk...
>
> > Daniel Pitts wrote:
> >> On Feb 16, 5:26 pm, Alex Hunsley <red...@bluebottle.com> wrote:
> >>> The matched parenthesis problem can be done with a non-deterministic
> >>> state machine, but not with a deterministic one.... hence no regular
> >>> expression can do it.
>
> I disagree, because a proof (by construction) exists which shows that
> any non-deterministic state machine can be converted to a determinisitc
> state machine. If the NDSM has K states, then DSM will have 2^K states. If
> you allow for infinite NDSM, it only seems fair that you also allow for
> infinite DSMs.
>
>
>
> >> Hmm, I don't think your definition is correct.
> >> Regex isn't always implementedwith a DSM, it might use NDA, which
> >> still doesn't solve it.
>
> > What do you mean by NDA? Non-deterministic automaton?
>
> Probably. I'll come back to this in a moment later in this post.
>
>
>
>
>
> >> In either case, the following is a deterministic state machine solves
> >> the problem.
>
> >> private static boolean isBalancedCount(String string) {
> >> int parens = 0;
> >> for (char c : string.toCharArray()) {
> >> if (c == '(') {
> >> ++parens;
> >> }
> >> if (c == ')' && --parens < 0) {
> >> return false;
> >> }
> >> }
> >> return parens == 0;
> >> }
>
> > Nope, it doesn't solve the problem. The int type in Java has finite
> > capacity - see Integer.MAX_VALUE - so more accurately this a finite
> > deterministic state machine. I'm actually trying to remember if
> > 'deterministic state machine' usually implies the 'finite' part in common
> > usage. A look at wikipedia seems to suggest that, but I wasn't looking at
> > it for long...
>
> The usually, when someone talks about deterministic automatons and
> non-deterministic automatons, they mean finite ones. So the usual
> abbreviations are DFA and NDFA. We can, of course, talk about infinite
> automatons, but there seems to be less literature on that topic (perhaps
> because it's equivalent to, but more complex than, some other machine, e.g.
> a push down stack machine or a Turing Machine or something, I don't know).
>
> So if you're talking about finite DAs and Nodes, then they cannot solve
> the "balance parentheses" problem. If you're talking about infinite ones,
> then if a NDA can solve it, so can a DA. And if a NDA cannot solve it,
> neither can a DA. The two are equivalent in power.
>
> 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.
>
> - Oliver

Its important to say that an NDA with K states has an equivalent DA
with at most 2^K states. The set of all NDA contains the set of all
Deterministic Automota. Determinism is a property of the stateful
automata.

For example, if you have the simple regex "abcd", the NDA and DA
produce the same graph, since it is only possible to be in one state
at a time. (s)->a->b->c->d->(e)

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

The DA actually has fewer "states" than the NDA inthis case (as b and
c are combined)

Daniel Pitts schrieb:
> On Feb 21, 9:21 am, "Oliver Wong" <o...@castortech.com> wrote:
>> "Alex Hunsley" <red...@bluebottle.com> wrote in message
>>
>> news:mmCBh.342519$MO2.286238@fe3.news.blueyonder.c o.uk...
>>
>>> Daniel Pitts wrote:
>>>> On Feb 16, 5:26 pm, Alex Hunsley <red...@bluebottle.com> wrote:
>>>>> The matched parenthesis problem can be done with a non-deterministic
>>>>> state machine, but not with a deterministic one.... hence no regular
>>>>> expression can do it.
>> I disagree, because a proof (by construction) exists which shows that
>> any non-deterministic state machine can be converted to a determinisitc
>> state machine. If the NDSM has K states, then DSM will have 2^K states. If
>> you allow for infinite NDSM, it only seems fair that you also allow for
>> infinite DSMs.
>>
>>
>>
>>>> Hmm, I don't think your definition is correct.
>>>> Regex isn't always implementedwith a DSM, it might use NDA, which
>>>> still doesn't solve it.
>>> What do you mean by NDA? Non-deterministic automaton?
>> Probably. I'll come back to this in a moment later in this post.
>>
>>
>>
>>
>>
>>>> In either case, the following is a deterministic state machine solves
>>>> the problem.
>>>> private static boolean isBalancedCount(String string) {
>>>> int parens = 0;
>>>> for (char c : string.toCharArray()) {
>>>> if (c == '(') {
>>>> ++parens;
>>>> }
>>>> if (c == ')' && --parens < 0) {
>>>> return false;
>>>> }
>>>> }
>>>> return parens == 0;
>>>> }
>>> Nope, it doesn't solve the problem. The int type in Java has finite
>>> capacity - see Integer.MAX_VALUE - so more accurately this a finite
>>> deterministic state machine. I'm actually trying to remember if
>>> 'deterministic state machine' usually implies the 'finite' part in common
>>> usage. A look at wikipedia seems to suggest that, but I wasn't looking at
>>> it for long...
>> The usually, when someone talks about deterministic automatons and
>> non-deterministic automatons, they mean finite ones. So the usual
>> abbreviations are DFA and NDFA. We can, of course, talk about infinite
>> automatons, but there seems to be less literature on that topic (perhaps
>> because it's equivalent to, but more complex than, some other machine, e.g.
>> a push down stack machine or a Turing Machine or something, I don't know).
>>
>> So if you're talking about finite DAs and Nodes, then they cannot solve
>> the "balance parentheses" problem. If you're talking about infinite ones,
>> then if a NDA can solve it, so can a DA. And if a NDA cannot solve it,
>> neither can a DA. The two are equivalent in power.
>>
>> 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.
>>
>> - Oliver
>
> Its important to say that an NDA with K states has an equivalent DA
> with at most 2^K states. The set of all NDA contains the set of all
> Deterministic Automota. Determinism is a property of the stateful
> automata.
>
> For example, if you have the simple regex "abcd", the NDA and DA
> produce the same graph, since it is only possible to be in one state
> at a time. (s)->a->b->c->d->(e)
>
> Whereas "a[bc]d" produces the NDA
> (s)->a
> / \
> b c
> \ /
> d->(e)
> and the DA
> (s)->a->b and c->d->(e)
>
> The DA actually has fewer "states" than the NDA inthis case (as b and
> c are combined)
>
>
>

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...