Формальные языки и автоматы VI: ω-алгебраические системы и трансдукторы
- Страницы / Pages
- 8-32
Аннотация
Это шестая статья в серии, дающей обзор некоторых разделов теории формальных языков и автоматов с использованием полуколец, формальных степенных рядов, матриц и теории неподвижных точек.
Рассмотрены основные результаты теории ω-алгебраических систем над квемикольцами, которые обобщают классические контекстно-свободные грамматики, порождающие языки над конечными и бесконечными словами. Представление этих результатов базируется на парах непрерывное полукольцо со звездой - омега-полумодуль.
Определены ω-алгебраические системы и охарактеризованы их решения порядка k через поведение конечных конечных алгебраических автоматов. Эти решения поставлены в соответствие с ω-контекстно-свободными языками. Затем вводятся рациональные и алгебраические трансдукторы и абстрактные ω-семейства степенных рядов над квемикольцами и доказывается, что рациональные и алгебраические степенные ряды конечных и бесконечных слов образуют такие абстрактные ω-семейства степенных рядов.