Теория формальных языков

С.С. Магазов

Теория формальных языков 

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

Учебно-методическое пособие

Федеральное государственное бюджетное  

образовательное учреждение высшего образования  

«Московский государственный технический университет имени Н.Э. Баумана  

(национальный исследовательский университет)»

УДК 512 
ББК 22.12 
        М12 
 
Издание доступно в электронном виде по адресу 
ebooks.bmstu.press/catalog/194/book2114.html 
 
Факультет «Информатика и системы управления» 
Кафедра «Теоретическая информатика  
и компьютерные технологии» 
 
Рекомендовано Научно-методическим советом  
МГТУ им. Н.Э. Баумана в качестве учебно-методического пособия 
 
Рецензент 
канд. техн. наук, доцент кафедры «Информационная безопасность»  
П.Г. Ключарёв 
 
 
 
Магазов, С. С. 
Теория формальных языков : Регулярные языки : учебнометодическое пособие / С. С. Магазов. — Москва : Издательство 
МГТУ им. Н. Э. Баумана, 2019. — 50, [2] с. : ил. 
 
ISBN 978-5-7038-5273-6 
 
Пособие содержит задания для лабораторных работ по темам: 
«Регулярные выражения», «Автоматные грамматики», «Лексический анализатор» и «Обработка текстовой информации с помощью регулярных выражений». Приведен необходимый для выполнения заданий теоретический материал.  
Для студентов, обучающихся по направлению подготовки 
01.03.02 «Прикладная математика и информатика». 
 
УДК 512 
ББК 22.12 
 
 

 МГТУ им. Н.Э. Баумана, 2019 
 Оформление. Издательство  
ISBN 978-5-7038-5273-6                                МГТУ им. Н.Э. Баумана, 2019 

М12 

Предисловие 

В МГТУ им. Н.Э. Баумана для студентов третьего курса об- 
учения в рамках направления подготовки «Прикладная математика 
и информатика» читается курс лекций по теории формальных языков. На лекционных занятиях подробно рассматриваются регулярные языки, которые имеют большое  практическое значение.  
Издание содержит материалы для проведения лабораторных 
работ по теории регулярных языков, включая следующие темы: 
«Регулярные выражения», «Автоматные грамматики», «Лексический анализатор». Приведены также материалы по технологии обработки текстовой информации с помощью языка регулярных выражений для С++. 
Пособие содержит большое количество вариантов заданий, что 
позволяет формировать индивидуальный пакет заданий в группах 
из 15 обучающихся. Часть заданий носит теоретический характер, 
для выполнения некоторых заданий требуется разработать программы. Перед каждой тематической группой заданий даны необходимые сведения из соответствующих разделов по теории регулярных языков.  
Предполагается, что обучающиеся усвоили курс дискретной 
математики, знакомы с принципами объектно-ориентированного 
программирования и языком C++.  
В результате выполнения лабораторных работ студент должен 
овладеть методами анализа текстовой информации и методами построения лексических анализаторов, которые являются важной частью транслятора. 

1. Языки слов 

Приведем основные определения из теории формальных языков. Конечное непустое множество символов (букв) ={a1,...,an} 
назовем алфавитом. В алфавит Σ может быть включен пустой 
символ (empty или dummy), который будем обозначать как e. Словом назовем конечную последовательность символов w=a0...ak, где 
ai . Включение в слово пустого символа e не меняет его.  
Дадим определение операций на словах. Конкатенацией слов 
называется бинарная операция, которая словам w и w′ ставит в соответствие слово, полученное приписыванием слова w′ в конец 
слова w. Конкатенацию обозначим как ww′.  
Множество всех слов алфавита Σ, включая пустое слово, обозначим как Σ*, а через  Σ+ обозначим Σ* без пустого слова. 
Определение 1.1. Языком над алфавитом Σ назовем подмно- 
жество слов из Σ*. Пустое подмножество также будем считать  
языком. 
Пусть L и L′ — языки над алфавитом Σ.  
Теоретико-множественные операции над языками:  
L+L′ — теоретико-множественное объединение языков;  
LL′ — теоретико-множественное пересечение языков;  
L\L′ — теоретико-множественная разность языков L и L′.  
Слово w принадлежит L\L′ тогда и только тогда, когда wL и  
wL′;  
Lс — дополнение языка L. Язык Lс состоит из слов Σ*, не входящих в язык L;  
LL′ — конкатенация языков, получается приписыванием к 
словам языка L слов языка L′. Будем i-й степенью языка L называть 
Li=L…L. Договоримся, что если хотя бы один из языков пуст, то их 
конкатенация LL′= — пустой язык. 
Итерацией  L* назовем объединение всех степеней языка Li 

плюс пустое слово 
*

0

i

i
L
L





+{e}.  

Дадим определение регулярного языка.  
Определение 1.2. Регулярное множество над алфавитом ∑ 
определяется следующей рекурсивной процедурой: 
пустое множество  — регулярное множество; 
{e} — регулярное множество; 
{a} — регулярное множество, где а∑. 
Если P и Q — регулярные множества, то:  
P + Q — регулярное множество; 
PQ — регулярное множество; 
P* — регулярное множество.  
Регулярное множество можно задать регулярным выражением, которое представляет собой формулу, построенную с помощью 
обозначений регулярных множеств, бинарных операций сложения 
и конкатенации, унарной операции итерации, а также скобок. 
Пример 1.1. Множество слов над алфавитом ={0, 1}, начинающихся с ‘0’ и заканчивающихся ‘1’, задается следующим регулярным выражением: 0{1,0}*1.  

Следующая лемма содержит тождества, позволяющие упрощать регулярные выражения. 
Лемма 1.1. О свойствах регулярных множеств  
P + Q = Q + P 
P + (Q + С)= (Q + P) + С 
P(QС) = (PQ)С 
P(Q + С) = PQ + PС 
(Q+С)P = QP + СP 
еA = Aе 
A* = A + A* 
A = A + A 

*=e 
A = A= 
(A*)*= A* 
A+ = A 
A* = e+A+ 
A+ = AA* 

Пример 1.2. Упростим выражение: A(A* +A)+B*=AA*+B*=  
= A++ B*. 
 

Контрольные вопросы 

1. Какой известной алгебраической структурой являются регулярные множества с операциями сложения и конкатенации? 

2. Есть ли регулярное множество, которое играет роль нуля 
для операции сложения? 
3. У любого ли регулярного множества есть обратный элемент 
для операции сложения? 
4. Есть ли регулярное множество, которое играет роль единицы для операции конкатенации? 

Лабораторная работа 1 

Цель — получить навыки построения регулярных выражений 
для заданного языка. 

Порядок выполнения лабораторной работы 

 В приложении 1 дан перечень неформальных описанных  
языков.  
1. Задайте язык регулярным выражением.  
2. Если возможно, упростите полученное регулярное выражение с помощью леммы 1.1.  
3. Оформите лабораторную работу согласно требованиям, 
приведенным в приложении 7.