Свойство замкнутости регулярных языков

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

Свойство позволяет создать распознаватель языка (построенного из двух других языков с помощью операций [конкатенации и т. п.]) механически соединив два автомата донорских языков. Но, поскольку, такой автомат содержит больше состояний, чем каждый из двух, то свойство замкнутости оказывается полезным инструментом для построения сложных автоматов.

Литература

• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений. — 2002. — 528 с. — ISBN 5-8459-0261-4.