Loading AI tools
Из Википедии, свободной энциклопедии
Регуля́рный язык (регуля́рное мно́жество) в теории формальных языков — множество слов, которое распознает некоторый конечный автомат. Класс регулярных множеств удобно изучать в целом, а полученные результаты оказываются применимы для достаточно широкого спектра формальных языков.
Пусть — конечный алфавит. Регулярными языками в алфавите называются множества слов, определяемые по индукции следующим образом:
Теорема Клини утверждает, что класс регулярных языков совпадает с классом языков распознаваемых конечным автоматом. Это значит, что для любого конечного автомата множество слов, которое он допускает является регулярным языком. И обратно, для любого регулярного языка существует автомат, которые допускает слова из этого языка и только их.
Данное понятие можно обобщить на произвольный моноид. Подмножество L моноида M называется распознаваемым над M, если существует конечный автомат над M, который принимает L. Конечный автомат над M — это автомат, который принимает на вход элементы из M. Семейство распознаваемых подмножеств моноида M обычно обозначается [1].
Так если M — свободный моноид над алфавитом , то семейство является просто семейством регулярных языков .
Существует аналог регулярного языка для множеств из сверхслов, бесконечных последовательностей над алфавитом. Индуктивно введём понятие общерегулярного множества (сверхслов), далее просто общерегулярное множество, над алфавитом :
Верен и аналог теоремы Клини - теорема Мак-Нотона, для её описания потребуется ввести ряд определений.
Буква сверхслова называется предельной, если существует последовательность , такая что .
Множество предельных букв сверхслова называют его пределом и пишут: .
Естественным образом можно определить работу автомата при подаче на него сверхслова.
Пусть - инициальный конечный автомат, - множество подмножеств алфавита , тогда автомат представляет с помощью выделенного набора подмножеств , если .
Подмножество называют сверхсобытием в алфавите .
Сверхсобытие называют представимым, если существует автомат и набор подмножеств множества , такие что автомат представляет это сверхсобытие с помощью .
Итак теорема Мак-Нотона утверждает, что множество представимых сверхсобытий совпадает с множеством общерегулярных множеств.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.