Регуля́рный язык (регуля́рное мно́жество) в теории формальных языков — формальный язык, который может быть выражен средствами регулярных выражений. Класс регулярных множеств удобно изучать в целом, а полученные результаты оказываются применимы для достаточно широкого спектра формальных языков.
Пусть — конечный алфавит. Регулярный язык в алфавите определяется следующими рекурсивными свойствами:
№. | Свойство | Описание |
---|---|---|
1 | Пустое множество является регулярным языком в алфавите Σ | |
2 | Язык, состоящей из одной лишь пустой строки, является регулярным языком в алфавите Σ | |
3 | Язык, состоящий из одного любого символа алфавита Σ, является регулярным языком в алфавите Σ | |
4 | Если два каких-либо языка являются регулярными в алфавите Σ, то и их объединение тоже является регулярным языком в алфавите Σ | |
5 | Если два каких-либо языка являются регулярными в алфавите Σ, то и язык, составленный из всевозможных сцеплений пар их элементов, тоже является регулярным в алфавите Σ | |
6 | Если какой-либо язык является регулярным в алфавите Σ, то язык из всевозможных сцеплений его элементов тоже является регулярным в алфавите Σ |
Ничто другое, кроме следующего из перечисленного, не является регулярным множеством в алфавите Σ
Данное понятие можно обобщить на произвольный моноид. Подмножество L моноида M называется распознаваемым над M, если существует конечный автомат над M, который принимает L. Конечный автомат над M — это автомат, который принимает на вход элементы из M. Семейство распознаваемых подмножеств моноида M обычно обозначается [1].
Так если M — свободный моноид над алфавитом , то семейство является просто семейством регулярных языков .
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .