Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Регулярные выражения




Определим следующие операции над множествами:

·

·

·

Тогда регулярные выражения над алфавитом T и языки, представляемые ими, могут быть определены следующим образом:

· Символ , представляющий пустое множество, является регулярным выражением.

· является регулярным выражением и представляет множество .

· Для каждого символа a является регулярным выражением и представляет множество {a}.

· Если p и q - регулярные выражения, представляющие множества P и Q , то (pq) , (p+q) и (p*) являются регулярными выражениями, представляющими множества PQ, и P* соответственно.

Отметим, что в этом определении подразумевается следующая система приоритетов: знак * обладает наивысшим приоритетом, за ним следует символ конкатенации, за которым следует символ |. Приоритеты можно изменять с помощью использования скобок.

Пример. Регулярное выражение 1(0+1)*1+1 представляет множество цепочек, начинающихся и заканчивающихся символом 1.

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

Пример. Рассмотренная выше грамматика для идентификатора может быть записана с помощью следующего регулярного выражения: Letter (Letter | Digit)*.


Поделиться:

Дата добавления: 2015-01-29; просмотров: 58; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты