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

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

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

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

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

  1. Пустое множество () является регулярным языком.
  2. Множество, состоящее из одной лишь пустой строки () является регулярным языком.
  3. Множество, состоящее из одного однобуквенного слова (, где ) является регулярным языком.
  4. Если и  — регулярные языки, то их объединение (), конкатенация () и взятие звездочки Клини () тоже являются регулярными языком.
  5. Других регулярных языков нет.

Связь автоматных и регулярных языков[править | править код]

Теорема Клини утверждает, что класс регулярных языков совпадает с классом языков распознаваемых конечным автоматом. Это значит, что для любого конечного автомата множество слов, которое он допускает является регулярным языком. И обратно, для любого регулярного языка существует автомат, которые допускает слова из этого языка и только их.

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

Данное понятие можно обобщить на произвольный моноид. Подмножество 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