Аннотация:
В статье определяются $(m,n)$-жесткие категориальные грамматики. Построен алгоритм, который по грамматике $G$ и числам $m$, $n$ определяет, является ли $G$$(m,n)$-жесткой. Доказано, что в классе $(m,n)$-жестких языков существует бесконечная иерархия, а также что класс $(m,n)$-жестких языков не сравним с классом регулярных языков. Исследуется сложность проблемы принадлежности для $(m,n)$-жестких грамматик.
Ключевые слова:формальные грамматики, категориальные грамматики, жесткие грамматики, алгоритм проверки жесткости, иерархия жестких языков, проблема принадлежности.
УДК:
519.766.23
Поступила в редакцию: 05.11.2017 Исправленный вариант: 02.12.2017