3 ms·
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.
by xelxebar 2y ago
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 https://en.wikipedia.org/wiki/Nested_word
Thanks for sharing!
- nsajko 2y agoAnother "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.