Аннотация:
В работе изучаются свойства обобщенных категориальных грамматик зависимостей (оКГЗ), введенных в работах [5,6]. Для них определяются нормальные формы, аналогичные нормальной форме Грейбах для кс-грамматик. Доказывается, что каждый оКГЗ-язык можно получить с помощью гомоморфизма из пересечения кс-языка и скобочного языка. Определен класс магазинных автоматов со счетчиками, которые допускают оКГЗ-языки.
Ключевые слова:формальные грамматики, категориальные грамматики, структура зависимостей, нормальные формы грамматик, магазинные автоматы со счетчиками.
УДК:
519.766.23
Поступила в редакцию: 27.11.2008 Исправленный вариант: 03.12.2008
Первая страница:
PDF файл