Регулярна мова

Нехай ${\displaystyle \Sigma }$ — скінченний алфавіт. Регулярна мова в цьому алфавіті визначається рекурсивно:

1. ${\displaystyle \emptyset }$ — пуста множина — це регулярна множина в алфавіті ${\displaystyle \Sigma }$
2. ${\displaystyle \varepsilon }$ — пусте слово — це регулярна множина в алфавіті ${\displaystyle \Sigma }$
3. ${\displaystyle \{a\},\ a\in \Sigma }$ — однолітерна множина — регулярна множина в алфавіті ${\displaystyle \Sigma }$
4. Якщо ${\displaystyle P}$ та ${\displaystyle Q}$ — регулярні множини, то такими є наступні множини:
   • ${\displaystyle P\cup Q}$ (операція об‘єднання);
   • ${\displaystyle P*Q}$ (операція конкатенації);
   • ${\displaystyle \{P\}={\varepsilon }\cup P\cup P*P\cup \ldots }$ (операція ітерації).
5. Ніякі інші множини, окрім побудованих на основі ПП 1-4 не є регулярними множинами.

«Стандартними» способами опису регулярної мови є представлення її у вигляді скінченного автомату, регулярної граматики, або ж регулярного виразу[1].

Регулярні мови замкнені відносно операцій об'єднання, перетину, конкатенації, доповнення та зірочки Кліні. Тобто, якщо ${\displaystyle L_{1}}$ та ${\displaystyle L_{2}}$ регулярні мови, тоді регулярними будуть мови: ${\displaystyle L_{1}\cup L_{2}}$, ${\displaystyle L_{1}\cap L_{2}}$, ${\displaystyle L_{1}L_{2}}$, ${\displaystyle L_{1}\emptyset }$, та ${\displaystyle L_{1}^{*}}$[4].

Існують й інші операції, відносно яких замкнені регулярні мови. Так, наприклад, гомоморфне відображення регулярної мови також є регулярною мовою. Таким чином, регулярні мови замкнені відносно гомоморфізму[5].

Крім того, для будь-якої регулярної мови у стандартному представленні існує алгоритм, що визначає приналежність заданого слова до цієї мови[6]. Стандартне представлення регулярної мови також дає можливість створити алгоритм, який би перевіряв чи ця мова порожня, скінченна, або ж нескінченна[7].

Стандартне представлення регулярних мов також дає можливість створити алгоритм, який би перевіряв їх на рівність[8].

• Ієрархія Чомскі
• Регулярна граматика