A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
1–10 of 38 posts
Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
#2One 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.
Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
#3The pictures of Brutalist architecture are awesome!
Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
#4[deleted]
Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
#5we’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.
Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
#6we’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.
you don't need a full counter. increment, decrement, and check_if_zero are enough. no need for get_value.
Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
#7we’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.
you don't need a full counter. increment, decrement, and check_if_zero are enough. no need for get_value.
you also need check_if_negative to detect close-before-open
Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
#8What is some further reading y'all could recommend on formal languages?
Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
#9What is some further reading y'all could recommend on formal languages?
sipser's theory of computation
Re: A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
#10we’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.
> Because in practice, everything is finite.
Indeed! https://neilmadden.blog/2019/02/24/why-you-really-can-parse-...