One 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.
"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).
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 stack.
If you're writing a parser and you want to report the location of an unclosed opening bracket then you need the actual stack.
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:
You just need as many counters as there are types of brackets. If any counter is non-zero at EOT or when a different type of right bracket is encountered then there's an unclosed left bracket of that type. And if a right bracket is encountered when its counter is zero then it's missing a left bracket of that type.
One 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.
"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).
To report the location of an unclosed opener you need a stack.
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 stack.
If you're writing a parser and you want to report the location of an unclosed opening bracket then you need the actual stack.
> Because in practice, everything is finite.
Indeed! https://neilmadden.blog/2019/02/24/why-you-really-can-parse-...
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
The counter is at 0, which indicates an error ... that plus the counter being non-zero when reaching the end of input is the entire point.
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.
You just need as many counters as there are types of brackets. If any counter is non-zero at EOT or when a different type of right bracket is encountered then there's an unclosed left bracket of that type. And if a right bracket is encountered when its counter is zero then it's missing a left bracket of that type.
The proof of non-regularity is a bit convoluted. You can easily apply the pumping lemma there
The pictures of Brutalist architecture are awesome!
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...
sipser's theory of computation