5 ms·
A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
- macintux 11mo agoOne of the few lessons I distinctly remember from college was finite automata in my PL class. I really enjoyed exploring the concepts and writing a grep tool; we were supposed to write either a NFA or DFA processing application, but I decided to write both. 20 years later I got to apply some of the same ideas to a language processing application, and it was such a pleasure to actually use something conceptual like that. Made me briefly regret landing in more hybrid infrastructure/automation roles instead of pure software development. Somewhere I may still have my copy of Preperata and Yeh that my professor recommended at the time for further reading. Like most of my books, it was never actually read, just sat around for years.
- senorqa 11mo agoThe pictures of Brutalist architecture are awesome!
- sevensor 11mo agoI 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.
- deleted 11mo ago[deleted]
- userbinator 11mo agowe’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.
- testaccount28 11mo agoyou don't need a full counter. increment, decrement, and check_if_zero are enough. no need for get_value.
- nmadden 11mo ago> Because in practice, everything is finite. Indeed! https://neilmadden.blog/2019/02/24/why-you-really-can-parse-html-and-anything-else-with-regular-expressions/ https://neilmadden.blog/2019/02/24/why-you-really-can-parse-...
- pfortuny 11mo agoYes. 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.
- Antibabelic 11mo agoWhat is some further reading y'all could recommend on formal languages?
- tehnub 11mo agosipser's theory of computation
- praptak 11mo agoThat's what I learnt from as part of CS curriculum at MiMUW. Can recommend: https://en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation https://en.wikipedia.org/wiki/Introduction_to_Automata_Theor...
- nmadden 11mo agoNot sure why you're being downvoted for recommending a classic textbook!
- praptak 11mo ago"But on a day-to-day basis, if asked to recognize balanced parentheses?" On day-to-day basis you will never encounter this problem in pure form. As the consequence the solutions are not good for the day-to-day stuff. Even if you only are only writting a verifier (which is already a bit unrealistic), you'll need to say something more than "not balanced". Probably rather something along the lines of "closing brace without a matching opening at [position]" or "[n] unclosed parentheses at <end of stream>" which rules out the simple recursive regex approach (counter still works).
- jibal 11mo agoTo report the location of an unclosed opener you need a stack.
- vidarh 11mo agoDepends. You want a stack, as it's certainly more efficient, but if you can rewind the position pointer you don't need one (you can count backwards). EDIT: It gets complicated if you need to count multiple different types of openers. In that case I think you need the stack, at least unless there are constraints on which openers can occur within others - you at the very least need to know which closer you're looking for right now, but if you can't deduce what is outside, you obviously then need to keep track of it. In practice, of course, we'll generally use a stack because it's just pointless to make life harder by not using one for this.
- jibal 11mo agoIf you've encountered 1 million unclosed parentheses, any or all of them could be unbalanced, so to report which ones are, you need 1 million pieces of information. The obvious way to organize them is as stack. Of course there are worse ways to do it. Rewinding the position pointer means that you've kept the entire input as a stack of characters, and now you have to keep track of all the closers on a stack in order to balance them with their openers. You NEED a stack. (And no, I didn't presume anything ... I addressed rewinding above.)
- firechickenbird 11mo agoThe proof of non-regularity is a bit convoluted. You can easily apply the pumping lemma there
- stefantalpalaru 11mo ago[dead]
- jgalt212 11mo agoBummer, I thought Reginald Braithwaite was publishing again. When I first entered JavaScript world, I really enjoyed and benefited from his writing and talks.
- a4isms 10mo agoHere 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.