Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

raganwald.com

Post reply on HN
Print view View original

31–38 of 38 posts

Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

#31

Post by jibal »

gpderetta wrote: post #20
jibal wrote: post #17

Earlier quoted context omitted.

The counter is simply the stack depth without bothering with the actual stack. If the stack is empty when you encounter a closer then it's unbalanced. If the stack isn't empty when you reach the end of the input then the items in the stack are unbalanced. If you have multiple kinds of brackets then you need the same number of counters. Each counter corresponds to the number of openers of that type currently on the st…

Wouldn't two counters report "([)]" as being properly balanced?

No, there's an open [ when the ) is encountered. The problem is the other way around -- my algorithm would report [() as an error. Oops, back to the drawing board. Clearly no counting can tell the difference between [() and ([).

Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

#32

Post by reuben364 »

_0ffh wrote: post #26
pfortuny wrote: post #11

Earlier quoted context omitted.

Yes. Actually, a more interesting example which does not complicate the statement (not the problem) too much is to check for nested parenthesis and brackets: (([[()])) -> ok ((([](])) -> not ok Hope OP gets this message.

In case anybody is interested, when we generalize the concept we're talking about Dyck languages. https://en.wikipedia.org/wiki/Dyck_language

I was surprised to not see a connection made to free groups in the article.

EDIT: The wikipedia article that is.

Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

#33

Post by spyrja »

jibal wrote: post #17
userbinator wrote: post #5

we’ll ask, “What’s the simplest possible computing machine that can recognize balanced parentheses?” A counter. That's the difference between theory and practice. Because in practice, everything is finite.

The counter is simply the stack depth without bothering with the actual stack. If the stack is empty when you encounter a closer then it's unbalanced. If the stack isn't empty when you reach the end of the input then the items in the stack are unbalanced. If you have multiple kinds of brackets then you need the same number of counters. Each counter corresponds to the number of openers of that type currently on the st…

FWIW it's a fairly straightforward algorithm. In C++:

  bool balanced(const string& text, const string& open, const string& close) {
    size_t length = text.size(), brackets = open.size();
    assert(close.size() == brackets);
    stack buffer;
    for (size_t index = 0; index

Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

#35

Post by nmadden »

praptak wrote: post #12
Antibabelic wrote: post #8

What is some further reading y'all could recommend on formal languages?

That's what I learnt from as part of CS curriculum at MiMUW. Can recommend: https://en.wikipedia.org/wiki/Introduction_to_Automata_Theor...

Not sure why you're being downvoted for recommending a classic textbook!

Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

#36

Post by sevensor »

senorqa wrote: post #3

The pictures of Brutalist architecture are awesome!

I was hoping for more captions on those, they’re quite fascinating. I wonder if the architects understood what a half century of weathering would do to the surface.

Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

#37

Post by agumonkey »

vidarh wrote: post #21
jibal wrote: post #17

Earlier quoted context omitted.

The counter is simply the stack depth without bothering with the actual stack. If the stack is empty when you encounter a closer then it's unbalanced. If the stack isn't empty when you reach the end of the input then the items in the stack are unbalanced. If you have multiple kinds of brackets then you need the same number of counters. Each counter corresponds to the number of openers of that type currently on the st…

You need the actual stack, I think, in the case of multiple types of openers without additional constraints, because if you just have raw counters you'd get tripped up by ([)] or similar. So to generalise your point you need a counter for each transition to a different type of opener. So (([])) needs only 2 counters, not 3. You could constrain it further if certain types of openers are only valid in certain cases so…

maybe there's an encoding that can allow counting different ordered accumulations succintly.. (thinking out loud here)

ps: apparently there's already a lot of research on multidimensional dyck languages (somehow mentionned below)

https://arxiv.org/pdf/2307.16522

https://omelkonian.github.io/data/publications/d3.pdf

Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

#38

Post by a4isms »

jgalt212 wrote: post #34

Bummer, I thought Reginald Braithwaite was publishing again. When I first entered JavaScript world, I really enjoyed and benefited from his writing and talks.

Here I am!

I still enjoy writing code like the code in TFA, but these days people seem a lot less interested in code than organizing their agentic LLMs, so I don't have the same incentive to share whatI find interesting. And it would be terrible marketing, like showing up to audition for a job driving F1... In a Jaguar E-Type.

Elegant and beautiful, but that isn't the game any more.

Post reply on HN