Регулярный язык

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Регуля́рный язык (регуля́рное мно́жество) в теории формальных языков — формальный язык, который может быть выражен средствами регулярных выражений. Класс регулярных множеств удобно изучать в целом, а полученные результаты оказываются применимы для достаточно широкого спектра формальных языков.

Определение[править | править вики-текст]

Пусть  — конечный алфавит. Регулярный язык в алфавите определяется следующими рекурсивными свойствами:

№. Свойство Описание
1 Пустое множество является регулярным языком в алфавите Σ
2 Язык, состоящей из одной лишь пустой строки, является регулярным языком в алфавите Σ
3 Язык, состоящий из одного любого символа алфавита Σ, является регулярным языком в алфавите Σ
4 Если два каких-либо языка являются регулярными в алфавите Σ, то и их объединение тоже является регулярным языком в алфавите Σ
5 Если два каких-либо языка являются регулярными в алфавите Σ, то и язык, составленный из всевозможных сцеплений пар их элементов, тоже является регулярным в алфавите Σ
6 Если какой-либо язык является регулярным в алфавите Σ, то язык из всевозможных сцеплений его элементов тоже является регулярным в алфавите Σ

Ничто другое, кроме следующего из перечисленного, не является регулярным множеством в алфавите Σ

Распознаваемое подмножество моноида[править | править вики-текст]

Данное понятие можно обобщить на произвольный моноид. Подмножество L моноида M называется распознаваемым над M, если существует конечный автомат над M, который принимает L. Конечный автомат над M — это автомат, который принимает на вход элементы из M. Семейство распознаваемых подмножеств моноида M обычно обозначается [1].

Так если M — свободный моноид над алфавитом , то семейство является просто семейством регулярных языков .

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Jean-Eric Pin, Mathematical Foundations of Automata Theory, Chapter IV: Recognisable and rational sets