|
Conference publicationsAbstractsXXVII conferenceРегулярность аддитивных полугрупп натуральных чиселЯрославский государственный университет им. П.Г. Демидова, каф. теоретической информатики, Россия, 150000, г. Ярославль, ул. Советская, 14, тел. (0852)45-8073, e-mail: belov@uniyar.ac.ru 1 pp. (accepted)Регулярность аддитивных полугрупп натуральных чисел Любой формальный алфавит, с точностью до изоморфизма, можно считать состоящим из «цифр» {0, 1, …, n-1}(см.[1]). Можно даже, без существенной потери содержания, считать, что рассматривается простейший бинарный 0-1–алфавит. Тогда любые цепочки символов данного алфавита, начинающиеся с 1, можно интерпретировать как записи натуральных чисел в двоичной позиционной системе счисления. В то же время любое множество таких цепочек является формальным языком в данном алфавите. При этом наиболее простые, так называемые регулярные языки (регулярные множества) замкнуты относительно таких языковых операций, как объединение, конкатенация, замыкание Клини – [1]. Таким образом возникает вопрос о связи свойств регулярной замкнутости и, например, аддитивной замкнутости. При этом оказывается справедливым такое утверждение: Теорема. Всякое множество натуральных чисел, замкнутое относительно сложения, является регулярным множеством. Другими словами, всякая аддитивная полугруппа натуральных чисел определяется некоторым конечным автоматом. Следствие. Пусть K – конечное множество натуральных чисел. Тогда множество всевозможных линейных комбинаций чисел из K с неотрицательными целыми коэффициентами является регулярным множеством. Литература 1. А. Хопкрофт, Дж. Ульман, Р. Мотвани. Введение в теорию автоматов, языков, и вычислений Москва, СПБ. Киев 2008
|
