News for hackers. Stuff that matters.

A comment on Regular, Recursive, Restricted. Parent comment

Re:Regular, Recursive, Restricted by xelxebar on Wednesday June 05, 2024 @07:39PM (#40591888)
Whoa. I've wondered about that exact question for a while, whether a proper class exists between RL and CFL. Relevant Wikipedia link, for posterity: https://en.wikipedia.org/wiki/Nested_word

Thanks for sharing!

[ Parent | on HN ]
Re:Regular, Recursive, Restricted by nsajko on Thursday June 06, 2024 @02:38AM (#40594252)
Another "proper class" are the operator precedence languages, AKA Floyd's languages (R. W. Floyd). They include the "visibly pushdown languages", which are really just a rediscovery of the input-driven languages. Floyd's languages are the languages parsed using the shunting yard algorithm.
[ Parent | on HN ]