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

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

ОпределениеПравить

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

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

Связь автоматных и регулярных языковПравить

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

Распознаваемое подмножество моноидаПравить

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

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

Общерегулярное множествоПравить

Существует аналог регулярного языка для множеств из сверхслов, бесконечных последовательностей над алфавитом. Индуктивно введём понятие общерегулярного множества (сверхслов), далее просто общерегулярное множество, над алфавитом  :

  1. Для любого регулярного языка   множество   - общерегулярно, где   - все возможные бесконечные последовательности слов из  .
  2. Объединение общерегулярных множеств - общерегулярно.
  3. Конкатенация регулярного языка и общерегулярного множества - общерегулярна, заметим, что конкатенация здесь имеет смысл только в этом порядке.

Верен и аналог теоремы Клини - теорема Мак-Нотона, для её описания потребуется ввести ряд определений.

Буква   сверхслова   называется предельной, если существует последовательность  , такая что  .
Множество предельных букв сверхслова   называют его пределом и пишут:  .

Естественным образом можно определить работу автомата при подаче на него сверхслова.

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

Итак теорема Мак-Нотона утверждает, что множество представимых сверхсобытий совпадает с множеством общерегулярных множеств.

См. такжеПравить

ПримечанияПравить

  1. Jean-Eric Pin, Mathematical Foundations of Automata Theory Архивная копия от 10 сентября 2014 на Wayback Machine, Chapter IV: Recognisable and rational sets

ЛитератураПравить

  • В. Б. Кудрявцев, С. В. Алешин, А. С. Подколзин. Введение в теорию автоматов. М., "Наука", 1985.
  • В. Б. Кудрявцев, С. В. Алешин, А. С. Подколзин. Элементы теории автоматов. М., изд-во МГУ, 1978.