Регулярні мови

Регулярна мова (регулярна множина) — формальна мова третього (найвужчого) класу в ієрархії Чомскі.

Регулярну мову можна задати регулярною граматикою або регулярним виразом, або ж ДСкА чи НДСкА, що її розпізнають.

Від контекстно-вільних мов регулярні відрізняються додатковими умовами: права частина правил виведення має бути порожнім словом, термінальним, нетермінальним, або нетермінальний вслід за яким стоїть термінальний символ.

Для визначення приналежності мови до класу регулярних існує Лема про накачку для регулярних мов та .

Означення

Нехай ${\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 не є регулярними множинами.

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

Теорія автоматів

Формальна мова є регулярною тоді й лише тоді, коли існує детермінований скінченний автомат здатний її розпізнати (акцептор).

При чому, для кожної регулярної мови можна побудувати недетермінований скінченний автомат, що її розпізнає. Та навпаки, кожен недетермінований скінченний автомат розпізнає певну регулярну мову.

Властивості

Регулярні мови замкнені відносно операцій об'єднання, перетину, конкатенації, доповнення та зірочки Кліні. Тобто, якщо ${\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}^{*}}$.

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

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

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

Примітки

1. (Розділ 4.2 в Linz)
2. Визначення 2.3 в: Peter Linz (January 2016). 2.1 Deterministic Finite Accepters. An Introduction to Formal Languages and Automata (вид. 6-те). Jones & Bartlett Learning. ISBN .
3. Теореми 3.4.1.2 та 3.4.1.3 в: by George Tourlakis (April 2012). 3.4 REGULAR GRAMMARS AND LANGUAGES. Theory of Computation. John Wiley & Sons. ISBN .
4. теорема 4.1 у Linz
5. теорема 4.3 у Linz
6. (теорема 4.5 у Linz)
7. (теорема 4.6 у Linz)
8. (теорема 4.7 у Linz)

Див. також

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