Регулярне безліч

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


Визначення регулярного безлічі

Нехай Σ - кінцевий алфавіт. Регулярне безліч R (Σ) в алфавіті Σ визначається наступними рекурсивними властивостями:

№. Властивість Опис
1 \ Varnothing \ in R (\ Sigma) Пусте безліч є регулярною множиною в алфавіті Σ
2 \ {\ Varepsilon \} \ in R (\ Sigma) Безліч, що складається з однієї лише порожній рядки є регулярною множиною в алфавіті Σ
3 \ Forall a \ in \ Sigma: \ {a \} \ in R (\ Sigma) Безліч, що складається з одного будь-якого символу алфавіту Σ є регулярною множиною в алфавіті Σ
4 P \ in R (\ Sigma) \ and Q \ in R (\ Sigma) \ Rightarrow (P \ cup Q) \ in R (\ Sigma) Якщо два-небудь безлічі є регулярними в алфавіті Σ, то і їх об'єднання теж є регулярною множиною в алфавіті Σ
5 P \ in R (\ Sigma) \ and Q \ in R (\ Sigma) \ Rightarrow PQ \ in R (\ Sigma) Якщо два-небудь безлічі є регулярними в алфавіті Σ, то й безліч, складене з всіляких зчеплень пар їх елементів теж є регулярною множиною в алфавіті Σ
6 P \ in R (\ Sigma) \ Rightarrow P ^ * \ in R (\ Sigma) Якщо будь безліч є регулярною в алфавіті Σ, то безліч всіляких зчеплень його елементів теж є регулярною множиною в алфавіті Σ

Ніщо інше, крім наступного з перерахованого, не є регулярним безліччю в алфавіті Σ