Внезапно правильно "теорема Хомского-Шютценберже". Это роли не играет, но неожиданный факт.
Ещё Дик на $\ge 2$ типах скобок генерирует full AFL (Abstract Families of Languages) (что бы это не значило)
Дик на одном типе скобок тоже генерирует full AFL --- one-counter языки. Всё это учение про разные семейства это не про сложность языков, а про замкнутость относительно различных операций. И старье это ужасное, изучалось в 70-х годах. Если хочешь это упомянуть в контексте сложности, то можно сказать, что Дик на $\ge 2$ типах скобок генерирует все КС-языки, а на одном типе --- только one-counter, которые являются только подклассом КС.
P.S. Скоро я должна понять то, что ты написала про interleaved, и добавить более содержательные комментарии :)
https://github.com/SiERic/bachelor-diploma-cfpq/blob/2a38047effda302c4b48453c5103165f77526b85/sections/dyck_1.tex#L135
Внезапно правильно "теорема Хомского-Шютценберже". Это роли не играет, но неожиданный факт.
Ещё Дик на $\ge 2$ типах скобок генерирует full AFL (Abstract Families of Languages) (что бы это не значило) Дик на одном типе скобок тоже генерирует full AFL --- one-counter языки. Всё это учение про разные семейства это не про сложность языков, а про замкнутость относительно различных операций. И старье это ужасное, изучалось в 70-х годах. Если хочешь это упомянуть в контексте сложности, то можно сказать, что Дик на $\ge 2$ типах скобок генерирует все КС-языки, а на одном типе --- только one-counter, которые являются только подклассом КС.
P.S. Скоро я должна понять то, что ты написала про interleaved, и добавить более содержательные комментарии :)