Отправить статью по E-mail 
АЛЬФА-МАТРИЦЫ И ГРАФ-ПОРОЖДЕННЫЕ ГРАММАТИКИ
- Авторы: Цветов В.П.1
-
Учреждения:
- Самарский национальный исследовательский университет имени академика С.П. Королева
- Выпуск: Том 23, № 1 (2017)
- Страницы: 28-40
- Раздел: Статьи
- URL: https://journals.ssau.ru/est/article/view/5144
- DOI: https://doi.org/10.18287/2541-7525-2017-23-1-28-40
- ID: 5144
Цитировать
Полный текст
Аннотация
В статье рассматривается обобщение граф-порожденных грамматик на основе их матричных представлений. Изучаются два класса граф-порожденных грамматик, связанные с вершинными и реберными разметками порождающих графов. Дается определение альфа-матрицы над полукольцом языков, заданных при помощи конечного алфавита A, и определяются соответствующие матричные алгебры. Введенные понятия в дальнейшем используются для конструктивного представления граф-порожденных языков и исследования вопросов, связанных с их эквивалентностью. Дается определение матрично порожденных грамматик как естественного надкласса граф-порожденных грамматик. Доказываемые утверждения иллюстрируются примерами.
Об авторах
В. П. Цветов
Самарский национальный исследовательский университет имени академика С.П. Королева
Автор, ответственный за переписку.
Email: morenov@ssau.ru
Россия
Список литературы
- Цветов В.П. Об одном надклассе A-грамматик. // Вестник СамГУ. Естественнонаучная серия. 2014. №10 (121). С. 102–108.
- Golan J.S. The Theory of Semirings with Applications in Mathematics and Theoretical Computer Science. Pitman, 1991. (Pitman Monographs and Surveys in Pure and Appl. Math.; Vol. 54).
- Hebisch U., Weinert H.J. Semirings. Algebraic Theory and Applications in Computer Science. Singapore: World Scientific, 1998.
- Молчанов В.А. О матричных полугруппах над полукольцами и их приложения к теории формальных языков // Математика. Механика: сб. науч. тр. Вып. 3. Саратов: Изд-во Сарат. ун-та, 2001. С. 98–101.
- Маслов В.П., Колокольцов В.Н. Идемпотентный анализ и его применение в оптимальном управлении. М.: Наука, 1994.
- Формальные языки и автоматы I: полукольца Конвея и конечные автоматы / С.И. Алешников // Вестник Калининградского государственнного университета. 2003. Вып. 3. С. 7–38.
- Формальные языки и автоматы II: непрерывные полукольца и алгебраические системы / С.И. Алешников // Вестник Калининградского государственнного университета. 2005. Вып. 1–2. С. 19–45.
- Исмагилов Р.С., Мастихина А.А. К вопросу частичного угадывания формальных языков // Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2016. № 2. C. 3-–15. doi: 10.18698/1812-3368-2016-2-3-15.
- Бисеров Д.С., Игудесман К.Б. Матрицы над полукольцом бинарных отношений и V-компонентные фракталы // Изв. вузов. Матем. № 5. 2011. С. 75–79.
- Цветов В.П. О специальном сужении конечного рефлексивного симметричного отношения до отношения эквивалентности // Вестник Самарского государственного университета. Естественнонаучная серия. 2006. № 4 (44). C. 26–47.
Дополнительные файлы
