Отправить статью по E-mail 
ОБ ОДНОМ НАДКЛАССЕ A-ГРАММАТИК
- Авторы: Цветов В.1
-
Учреждения:
- Самарский государственный университет
- Выпуск: Том 20, № 10 (2014)
- Страницы: 102-108
- Раздел: Статьи
- URL: https://journals.ssau.ru/est/article/view/4515
- DOI: https://doi.org/10.18287/2541-7525-2014-20-10-102-108
- ID: 4515
Цитировать
Полный текст
Аннотация
В статье рассматривается класс грамматик, допускающих представление правил порождения при помощи алгоритмов нахождения маршрутов на графах. Дается определение граф-порожденной грамматики или G-грамматики (над алфавитом A ) в терминах семейств маршрутов на вершинно размеченных графах. В отличие от графовых грамматик, которые применяются для описания динамики графовых структур, G-грамматики, напротив, используют граф-отношения в качестве средства представления формальных языков. Приводится алгоритм построения G-грамматики, порождающей язык, рас- познаваемый детерминированным конечным автоматом. Показывается, что класс языков, порождаемых G-грамматиками, является строгим надмножеством регулярных языков.
Об авторах
В.П. Цветов
Самарский государственный университет
Автор, ответственный за переписку.
Email: morenov.sv@ssau.ru
Список литературы
- Хомский H. О некоторых формальных свойствах грамматик // Кибернетический сборник. 1962. № 5. С. 279-311.
- Хомский H. Заметка о грамматиках непосредственных составляющих // Кибернетический сборник. 1962. № 5. С. 312-316.
- Хомский H. Формальные свойства грамматик // Кибернетический сборник, новая серия. 1966. № 2. С. 121-230.
- Глушков В.М. Абстрактная теория автоматов // Успехи математических наук. 1961. Т. 16. № 5. С. 3-62.
- Глушков В.М. Теория автоматов и вопросы проектирования структур цифровых машин // Кибернетика. 1965. № 1. С. 3-11.
- Глушков В.М. Теория автоматов и формальные преобразования микропрограмм // Кибернетика. Т. 1. № 5. 1965. С. 1-9.
- Петров С.В. Графовые грамматики и автоматы (обзор) // Автоматика и телемеханика. 1978. № 7. С. 116-136.
- Balasubramanian D., Narayanan A., Buskirk C.P. et al. The Graph Rewriting and Transformation Language: GReAT // Electronic Communications of the EASST. 2006. Vol. 1. P. 1-8.
- Pfaltz J., Rosenfeld A. Web Grammars // Proceedings of the 1st International Joint Conference on Artificial Intelligence. 1969. P. 609-620.
- Rekers J., Schuerr A. A Graph Grammar approach to Graphical Parsing // Proceedings of the 11th IEEE International Symposium, 1995. P. 195-202.
Дополнительные файлы
