Алгебры языков, представимых в отмеченных графах

Abstract

В работе исследованы основные особенности алгебры языков, представимых в графах с отмеченными вершинами, и изучена взаимосвязь этой алгебры и алгебры языков, распознаваемых конечными автоматами. Показано, что класс языков, представимых регулярными выражениями рассматриваемой алгебры, совпадает с классом всех регулярных языков, не содержащих пустого слова, Доказано существование изоморфных подалгебр у рассмотренных алгебр. Получены отображения, позволяющие по регулярным выражениям одной алгебры переходить к регулярным выражениям другой алгебры, представляющим тот же язык. Показано, что алгебра языков, представимых в графах с отмеченными вершинами, не является алгеброй Клини, и между этой алгеброй и алгеброй регулярных, языков нет гомоморфизма.