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

С.С. Магазов

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

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

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

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

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

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

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

УДК 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. 
 

2. Автоматная грамматика 

Автоматная грамматика — самый простой вид грамматик. Эти 
грамматики широко используются при проектировании трансля- 
торов.  
Определение 2.1. Праволинейной грамматикой называется 
четверка G=(N,,P,S): 
N={A1…Ak,S} — множество нетерминальных символов;  
={a1…al} — множество терминальных символов;  
P — множество правил вывода. Каждое правило имеет вид 
AiBiw, или S Biw, где w* и S, Bi, AiN;  

S — начальный или выделенный символ. 
Если правила вывода имеют вид AiwBi, то грамматика называ-
ется леволинейной. Автоматной грамматикой называется граммати-
ка, которая либо праволинейная, либо леволинейная. 
Определение 2.2  
1. Выводом в грамматике G называется последовательность 
слов S, w1…wn, причем, если wi, и wi+1 — любые два смежных сло-
ва, то они должны иметь вид wi=Ai , wi+1=v и в G должно 
найтись правило вывода вида Aiv.  
2. Слово w, имеющее вывод в грамматике G, называется вы-
водимым в G словом. 
3. Предложением (терминальным словом) называется выво-
димое в грамматике G слово, состоящее из терминальных символов.  
4. Языком грамматики L(G) называется множество выводи-
мых терминальных слов.  
Пример 2.1. Пусть L — язык над алфавитом ={0,1}, каждое 
слово которого состоит из подслов, состоящих из четного числа 
нулей, и подслов, состоящих из четного число единиц. Определим 
грамматику, задающую язык L: 
SA|B|e 
 
B00В|S 
ВS 
A11A  
AS 

Вывод слова 000011: 
S; В; 00В; 0000B; 0000S; 000011A; 00011  
Определение 2.3. Грамматики G1 и G2 эквивалентны, если 

L(G1)=L(G2).  

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

1. Являются ли праволинейные и леворекурсивные граммати-

ки эквивалентными? 

2. Можно ли один и тот же язык задать различными грамма-

тиками? 

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

Цель — получить навыки построения автоматных грамматик 

для заданных языков и построение выводов слов.  

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

1. По описанию языка из приложения 1 построить автомат-

ную грамматику.  

2. В приложении 2 язык задан регулярным выражением:  

а) если возможно, упростить регулярное выражение;  
б) построить по регулярному выражению эквивалентную 

грамматику. Построить вывод для заданного в таблице слова (см. 
приложение 2).  

3. Оформить лабораторную работу согласно требованиям, при-

веденным в приложении 7. 

 

3. Конечные автоматы-распознаватели 

Регулярные языки можно задавать с помощью конечных авто-
матов-распознавателей. Распознаватель легко реализовать на прак-
тике как в виде программы, так и в виде электронного устройства.  
Определение 3.1. Недетерминированный распознаватель  
Буша задается пятеркой AS0=(S, , , S0, F), где: 
S ={s0…sm} — конечное множество состояний;  
={a0…an} — конечное множество входных символов (вход-
ной алфавит);  
δ(x,y,z) — отношение переходов δSS (transition relation);  
S0S — подмножество начальных состояний; 
FS — подмножество конечных состояний.  
Если на вход распознавателя, находящегося в состоянии s, по-
ступил символ a, и в отношении δ есть по крайней мере два ребра 
s,a,s′δ, s,a,sδ, то  распознаватель может перейти как  
в состояние s′, так и в состояние s. В этом заключается недетер-
минированность распознавателя.  
Недетерминированные распознаватели часто используются  
в теоретических построениях, так как с их помощью легче записы-
вать сложные алгоритмы поведения автоматов.  
Дадим определение важному частному случаю недетермини-
рованного распознавателя, а именно детерминированному распо-
знавателю. 
Определение 3.2. Детерминированный распознаватель зада-
ется пятеркой As0=(S,,δ,s0,F), где: 
S ={s0…sm} — конечное множество состояний;  
={a0…an} — конечное множество входных символов (вход-
ной алфавит);  
δ(s,a) — функция переходов δ:SS; 
s0S — начальное состояние; 
FS — подмножество конечных состояний.  

Рассмотрим способы задания автоматов. Конечные множества 
S и  задаются перечислением элементов. Функцию переходов 
можно задать различными способами. Здесь рассмотрим таблич-
ный способ задания функции переходов: 

S/
a0 
… 
an 

s0 
01
b
 
…
0n
b
 

… 
… 
…
… 

sm 
0m
b
…
mn
b

В верхнем ряду перечислены символы входного алфавита ,  
в левом столбце состояния S. На пересечении i строки и j-го 
столбца стоит значение функции переходов 
ij
b =δ(si,aj). В случае 

детерминированного преобразователя это просто состояние 
ij
b S. 

В случае недетерминированного преобразователя это подмноже-
ство состояний 
ij
b S. Допускается, что отношение (функция) δ 

может быть не определено на некоторых значениях аргументов.  
В этом случае распознаватель называют частичным. Распознава-
тель, у которого функция переходов всюду определена, называется 
полным. 
Пример 3.1. Детерминированный распознаватель A1:  
S={s0,s1,s2,sf} — множество внутренних состояний; 
={1,2} — входной алфавит; 
s0 — начальное состояние; 
sf — конечное состояние; 
δ(x,y) — функция переходов. Задается следующей таблицей: 

S/
1 
2 

s0 
s1 
s2

s1 
sf 
s1

s2 
s2
sf 

sf 
sf 
sf 

 
Пример 3.2. Зададим недетерминированный распознаватель A2:  
S={s0,s1,s2,sf} — множество внутренних состояний; 
={1,2} — входной алфавит;