Регулярный язык
 |
Эта страница требует существенной переработки. Возможно, её необходимо викифицировать, дополнить или переписать.
Пояснение причин и обсуждение — на странице Википедия:К улучшению/22 сентября 2016. |
Регуля́рный язык (регуля́рное мно́жество) в теории формальных языков — формальный язык, который может быть выражен средствами регулярных выражений. Класс регулярных множеств удобно изучать в целом, а полученные результаты оказываются применимы для достаточно широкого спектра формальных языков.
Определение
Пусть <math>\Sigma</math> — конечный алфавит. Регулярный язык <math>R(\Sigma)</math> в алфавите <math>\Sigma</math> определяется следующими рекурсивными свойствами:
| №. | Свойство | Описание |
|---|---|---|
| 1 | <math>\varnothing \in R(\Sigma)</math> | Пустое множество является регулярным языком в алфавите Σ |
| 2 | <math>\{\varepsilon\} \in R(\Sigma)</math> | Язык, состоящей из одной лишь пустой строки, является регулярным языком в алфавите Σ |
| 3 | <math>\forall a \in \Sigma: \{a\} \in R(\Sigma)</math> | Язык, состоящий из одного любого символа алфавита Σ, является регулярным языком в алфавите Σ |
| 4 | <math>P \in R(\Sigma) \and Q \in R(\Sigma) \Rightarrow (P \cup Q) \in R(\Sigma)</math> | Если два каких-либо языка являются регулярными в алфавите Σ, то и их объединение тоже является регулярным языком в алфавите Σ |
| 5 | <math>P \in R(\Sigma) \and Q \in R(\Sigma) \Rightarrow PQ \in R(\Sigma)</math> | Если два каких-либо языка являются регулярными в алфавите Σ, то и язык, составленный из всевозможных сцеплений пар их элементов, тоже является регулярным в алфавите Σ |
| 6 | <math>P \in R(\Sigma) \Rightarrow P^* \in R(\Sigma)</math> | Если какой-либо язык является регулярным в алфавите Σ, то язык из всевозможных сцеплений его элементов тоже является регулярным в алфавите Σ |
Ничто другое, кроме следующего из перечисленного, не является регулярным множеством в алфавите Σ
Распознаваемое подмножество моноида
Данное понятие можно обобщить на произвольный моноид. Подмножество L моноида M называется распознаваемым над M, если существует конечный автомат над M, который принимает L. Конечный автомат над M — это автомат, который принимает на вход элементы из M. Семейство распознаваемых подмножеств моноида M обычно обозначается <math>\mathrm{Rec}(M)</math>[1].
Так если M — свободный моноид <math>\Sigma^*</math> над алфавитом <math>\Sigma</math>, то семейство <math>\mathrm{Rec}\left(\Sigma^*\right)</math> является просто семейством регулярных языков <math>\mathrm{Reg}\left(\Sigma^*\right)</math>.
См. также
Напишите отзыв о статье "Регулярный язык"
Примечания
- ↑ Jean-Eric Pin, [www.liafa.jussieu.fr/~jep/PDF/MPRI/MPRI.pdf Mathematical Foundations of Automata Theory], Chapter IV: Recognisable and rational sets
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Регулярный язык
– Ты лучше не беспокойся. Мне что нужно, я просить не стану, сам возьму.– Да что ж, я так…
– Ну, и я так.
– Прощай.
– Будь здоров…
… и высоко, и далеко,
На родиму сторону…
Жерков тронул шпорами лошадь, которая раза три, горячась, перебила ногами, не зная, с какой начать, справилась и поскакала, обгоняя роту и догоняя коляску, тоже в такт песни.
Возвратившись со смотра, Кутузов, сопутствуемый австрийским генералом, прошел в свой кабинет и, кликнув адъютанта, приказал подать себе некоторые бумаги, относившиеся до состояния приходивших войск, и письма, полученные от эрцгерцога Фердинанда, начальствовавшего передовою армией. Князь Андрей Болконский с требуемыми бумагами вошел в кабинет главнокомандующего. Перед разложенным на столе планом сидели Кутузов и австрийский член гофкригсрата.
– А… – сказал Кутузов, оглядываясь на Болконского, как будто этим словом приглашая адъютанта подождать, и продолжал по французски начатый разговор.
– Я только говорю одно, генерал, – говорил Кутузов с приятным изяществом выражений и интонации, заставлявшим вслушиваться в каждое неторопливо сказанное слово. Видно было, что Кутузов и сам с удовольствием слушал себя. – Я только одно говорю, генерал, что ежели бы дело зависело от моего личного желания, то воля его величества императора Франца давно была бы исполнена. Я давно уже присоединился бы к эрцгерцогу. И верьте моей чести, что для меня лично передать высшее начальство армией более меня сведущему и искусному генералу, какими так обильна Австрия, и сложить с себя всю эту тяжкую ответственность для меня лично было бы отрадой. Но обстоятельства бывают сильнее нас, генерал.
И Кутузов улыбнулся с таким выражением, как будто он говорил: «Вы имеете полное право не верить мне, и даже мне совершенно всё равно, верите ли вы мне или нет, но вы не имеете повода сказать мне это. И в этом то всё дело».
Австрийский генерал имел недовольный вид, но не мог не в том же тоне отвечать Кутузову.
– Напротив, – сказал он ворчливым и сердитым тоном, так противоречившим лестному значению произносимых слов, – напротив, участие вашего превосходительства в общем деле высоко ценится его величеством; но мы полагаем, что настоящее замедление лишает славные русские войска и их главнокомандующих тех лавров, которые они привыкли пожинать в битвах, – закончил он видимо приготовленную фразу.
Кутузов поклонился, не изменяя улыбки.
– А я так убежден и, основываясь на последнем письме, которым почтил меня его высочество эрцгерцог Фердинанд, предполагаю, что австрийские войска, под начальством столь искусного помощника, каков генерал Мак, теперь уже одержали решительную победу и не нуждаются более в нашей помощи, – сказал Кутузов.
