Регулярна мова (регулярна множина) — формальна мова третього (найвужчого) класу в ієрархії Чомскі.
Регулярну мову можна задати регулярною граматикою або регулярним виразом, або ж ДСкА чи НДСкА, що її розпізнають.
Від контекстно-вільних мов регулярні відрізняються додатковими умовами: права частина правил виведення має бути порожнім словом, термінальним, нетермінальним, або нетермінальний вслід за яким стоїть термінальний символ.
Для визначення приналежності мови до класу регулярних існує Лема про накачку для регулярних мов та теорема Майхілла-Нероде.
Означення Нехай — скінченний алфавіт. Регулярна мова в цьому алфавіті визначається рекурсивно: — пуста множина — це регулярна множина в алфавіті — пусте слово — це регулярна множина в алфавіті — однолітерна множина — регулярна множина в алфавіті Якщо та — регулярні множини, то такими є наступні множини: (операція об‘єднання); (операція конкатенації); (операція ітерації). Ніякі інші множини, окрім побудованих на основі ПП 1-4 не є регулярними множинами.
«Стандартними» способами опису регулярної мови є представлення її у вигляді скінченного автомата, регулярної граматики, або ж регулярного виразу(Розділ 4.2 в Linz).
Теорія автоматів
Формальна мова є регулярною тоді й лише тоді, коли існує детермінований скінченний автомат здатний її розпізнати (акцептор)Визначення 2.3 в: .
При чому, для кожної регулярної мови можна побудувати недетермінований скінченний автомат, що її розпізнає. Та навпаки, кожен недетермінований скінченний автомат розпізнає певну регулярну мовуТеореми 3.4.1.2 та 3.4.1.3 в: .
Властивості
Регулярні мови замкнені відносно операцій об'єднання, перетину, конкатенації, доповнення та зірочки Кліні. Тобто, якщо та регулярні мови, тоді регулярними будуть мови: , , , , та теорема 4.1 у Linz.
Існують й інші операції, відносно яких замкнені регулярні мови. Так, наприклад, гомоморфне відображення регулярної мови також є регулярною мовою. Таким чином, регулярні мови замкнені відносно гомоморфізмутеорема 4.3 у Linz.
Крім того, для будь-якої регулярної мови у стандартному представленні існує алгоритм, що визначає приналежність заданого слова до цієї мови(теорема 4.5 у Linz). Стандартне представлення регулярної мови також дає можливість створити алгоритм, який би перевіряв чи ця мова порожня, скінченна, або ж нескінченна(теорема 4.6 у Linz).
Стандартне представлення регулярних мов також дає можливість створити алгоритм, який би перевіряв їх на рівність(теорема 4.7 у Linz).
Примітки
Див. також Ієрархія Чомскі Регулярна граматика