Математическая логика, алгебра, теория чисел и дискретная математика

Определимость множеств в теориях языков с операциями объединения и итерации

Б. Н. Карлов

Тверской государственный университет, г. Тверь

Аннотация: В работе исследованы теории языков в различных алфавитах с операциями объединения и итерации. Доказано, что в случае однобуквенного алфавита в такой теории определима операция возведения языка, содержащего единственное слово, в любую фиксированную степень. Как следствие, установлена определимость всех конечных языков и всех языков с конечными дополнениями. Доказано, что в случае многобуквенного алфавита неопределимы некоторые конечные языки. Установлено, что, независимо от алфавита, определимы языки, не являющиеся контекстно-свободными.

Ключевые слова: формальный язык, теория, объединение, итерация, определимость.

УДК: 510.67, 519.766

Поступила в редакцию: 30.05.2025
Исправленный вариант: 24.06.2025

DOI: 10.26456/vtpmk734

Реферативные базы данных:

•