Регулярный язык. Способы задания регулярных языков Теория формальных языков для чайников

В этой главе мы начинаем изложение элементов теории формальных языков.

Говоря "формальный язык", мы имеем в виду то, что приведенные здесь результаты используются прежде всего при описании искусственных языков, придуманных людьми для специальных целей, например языков программирования. Но непреодолимой преграды между специально придуманными искусственными (формальными) языками и стихийно возникающими и развивающимися естественными языками не существует. Оказывается, что естественные языки характеризуются сложными грамматическими правилами, т.е. довольно жестко формализованы, а даже самый "научно разработанный" язык программирования содержит "темные места", однозначное понимание которых является проблемой.

Изучая языки, следует иметь в виду три основных аспекта.

Первый из них - синтаксис языка . Язык - это какое- то множество "слов", где "слово" есть определенная конечная последовательность "букв" - символов какого-то заранее фиксированного алфавита. Термины "буква" и "слово" могут пониматься по-разному (математическое определение этих терминов будет дано ниже). Так, "буквами" могут быть действительно буквы алфавита какого-нибудь естественного или формального языка, например русского языка или языка программирования "Паскаль". Тогда "словами" будут конечные последовательности "букв": крокодил", "integer ". Такие слова называют "лексемами". Но "буквой" может быть "слово" ("лексема") в целом. Тогда "слова" - это предложения естественного языка или программы языка программирования. Если фиксировано какое-то множество "букв", то не каждая их последовательность будет "словом", т.е. Элексемой" данного языка, а только такая последовательность, которая подчиняется определенным правилам. Слово "крыкадил" не является лексемой русского языка, а слово "iff" не является лексемой в "Паскале". Предложение "Я люблю ты" не является правильным предложением русского языка, точно так же, как и запись "х:= =t" не есть правильно написанный оператор присваивания "Паскаля". Синтаксис* языка и представляет собой систему правил, в соответствии с которыми можно строить "правильные" последовательности "букв". Каждое слово языка характеризуется определенной структурой, специфичной именно для данного языка. Тог да необходимо, с одной стороны, разработать механизмы перечисления, или порождения, слов с заданной структурой, а с другой - механизмы проверки того, что данное слово принадлежит данному языку. Прежде всего именно:эти механизмы и изучает классическая теория формальных языков.

Второй аспект - семантика языка . Семантика** предполагает сопоставление словам языка некоего "смысла", Эзначения". Например, записывая математическую формулу, мы должны соблюдать определенные синтаксические правила (расстановка скобок, правописание символов, порядок символов и т.п.), но, кроме этого, формула имеет вполне определенный смысл, что-то обозначает.

Язык - это средство общения, передачи информации. Если мы хотим, чтобы нас поняли, мы должны не только синтаксически правильно, соблюдая должный порядок букв в слове и слов в предложении, строить свою речь, но и заботиться об ее смысле, о тех идеях, которые мы выражаем в речи. Математические теории "смысла" появились сравнительно недавно, и в дополнении к следующей главе мы очень коротко рассмотрим некоторые подходы к математическому описанию семантики языков программирования.

* Слово "синтаксис" происходит от древнегреческих "syn" - "вместе" и "taxis" - "порядок, строй". Таким образом, синтаксис можно понимать как "составление".

** От древнегреческих слов "sema" - "знак, знамение" и "semanticos" - "обозначающий".

Наконец, третий аспект - прагматика языка . Прагматика связана с теми целями, которые ставит перед собой носитель языка: например, человек произносит речь, имея перед собой цели, связанные не с синтаксисом, не с семантикой языка, на котором он говорит или пишет, а, скажем, с получением за речь определенной суммы денег. Прагматика является уже скорее дисциплиной социально-философской, затрагивающей целепол агающую деятельность личности. Мы ни в малейшей степени не будем ее касаться.

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

• Алфавит, слово, язык

• Порождающие грамматики

  Как уже отмечалось, классическая теория формальных языков изучает прежде всего синтаксис языка. Она вводит математическую модель синтаксиса, которая описывает механизмы порождения и распознавания "правильно построенных" цепочек. В этом разделе мы рассмотрим первый из этих механизмов.

операции объединения языков мы знаем. Определим операции конкатенации и итерации (иногда ее называют замыканием Клини).

Пусть L 1 и L 2 - языки в алфавите

Тогда , т.е. конкатенация языков состоит из конкатенаций всех слов первого языка со всеми словами второго языка. В частности, если , то , а если , то .

Введем обозначения для "степеней" языка L :

Таким образом в L i входят все слова, которые можно разбить на i подряд идущих слов из L .

Итерацию (L) * языка L образуют все слова которые можно разбить на несколько подряд идущих слов из L :

Ее можно представить с помощью степеней:

Часто удобно рассматривать "усеченную" итерацию языка, которая не содержит пустое слово , если его нет в языке: . Это не новая операция, а просто удобное сокращение для выражения .

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

В следующей таблице приведено формальное индуктивное определение регулярных выражений над алфавитом и представляемых ими языков.

Выражение r	Язык L r
	L a ={a}
Пусть r 1 и r 2 -это	L r1 и L r2 -представляемые
регулярные выражения .	ими языки.
Тогда следующие выражения
являются регулярными	и представляют языки:
r=(r 1 +r 2)
r=(r 1 circr 2)
r=(r 1) *	L r =L r1 *

При записи регулярных выражений будем опускать знак конкатенации и будем считать, что операция * имеет больший приоритет, чем конкатенация и + , а конкатенация - больший приоритет, чем + . Это позволит опустить многие скобки. Например, можно записать как 10(1 * + 0) .

Определение 5.1 . Два регулярных выражения r и p называются эквивалентными, если совпадают представляемые ими языки, т.е. L r =L p . В этом случае пишем r = p .

Нетрудно проверить, например, такие свойства регулярных операций:

• r + p= p+ r (коммутативность объединения),
• (r+p) +q = r + (p+q) (ассоциативность объединения),
• (r p) q = r (p q) (ассоциативность конкатенации),
• (r *) * = r * (идемпотентность итерации ),
• (r +p) q = rq + pq (дистрибутивность).

Пример 5.1 . Докажем в качестве примера не столь очевидное равенство : (r + p) * = (r * p *) * .

Пусть L 1 - язык, представляемый его левой частью, а L 2 - правой. Пустое слово принадлежит обоим языкам. Если непустое слово , то по определению итерации оно представимо как конкатенация подслов, принадлежащих языку . Но этот язык является подмножеством языка L"=L r * L p * (почему?). Поэтому . Обратно, если слово , то оно представимо как конкатенация подслов, принадлежащих языку L" . Каждое из таких подслов v представимо в виде v= v 1 1 ... v k 1 v 1 2 ... v l 2 , где для всех i=1, ... , k подслово и для всех j=1, ... , l подслово (возможно, что k или l равно 0). Но это значит, что w является конкатенацией подслов, каждое из которых принадлежит и, следовательно, .

Теория автоматов - это раздел теории управляющих систем , изучающий математические модели преобразователей дискретной информации, называемые автоматами . С определенной точки зрения такими преобразователями являются как реальные устройства (вычислительные машины, автоматы, живые организмы и т.д.), так и абстрактные системы (например, формальная система, аксиоматические теории и т.д.), благодаря чему возможно применение теории автоматов в различных научных и прикладных исследованиях. Наиболее тесно теория автоматов связана с математической логикой и теорией алгоритмов. В частности, средствами теории автоматов доказывается разрешимость некоторых формальных исчислений.

Еще одним важнейшим объектом изучения в данном курсе является формальный язык 1 – произвольное множество слов некоторого алфавита. Важность формальных языков для теоретической информатики обусловлена тем, что наиболее простой и удобной моделью данных, используемых в компьютерных программах, является конечная последовательность, каждый элемент которой взят из некоторого заранее зафиксированного конечного множества. Поскольку используемые в приложениях формальные языки, как правило, являются бесконечными, то нужен способ конечного описания формального языка. В данном курсе будем изучать 3 классических средства такого описания: автоматы , регулярные выражения и порождающие грамматики .

Введение

1. Начальные понятия теории формальных языков

Рассмотрим непустое конечное множество А , состоящее из символов {a 1 , …, a k }. Будем называть А алфавитом , а его символы – буквами . Всякая конечная последовательность букв этого алфавита называется словом (цепочкой или строкой ): w =a 1 a 2 …a n – слово (a i A ), |w | – длина слова (число букв, из которых состоит слово, причем каждый символ встречается столько раз, сколько раз он встречается в w ). Через |w | b обозначим количество вхождений символа b в слово w .

Бесконечная последовательность букв алфавита А называется сверхсловом , - сверхслово из бесконечного числа букв а . Пустым называется слово, не содержащее ни одной буквы. Оно обозначается через . Очевидно, ||=0.

- множество слов алфавита А длины n . Множество всех слов алфавита А (включая сверхслова) обозначается А *. Это множество счетное, поскольку является объединением счетного числа конечных множеств
. Множество всех непустых слов в алфавите А обозначается А + . Если A ={a }, то А *={a }* будем обозначать через а *.

Любое подмножество
называетсяязыком (формальным языком ) над алфавитом А .

Если x и y – слова языка
, то слово ху (результат приписывания слова у в конце слова х ) называется конкатенацией (сцеплением , произведением ) слов х и у .
(n раз берем х ). Положим
.

Говорят, что слово х – подслово слова у , если y =uxv для некоторых слов u и v . Все подслова слов языка
образуютмножество подслов языка L , которое обозначается через Subw(L ).

Примеры . 1. ba 3 =baaa ,
- в данном слове есть подслова ab , aba , ba и т.п.

2. Множество {a , abb } - язык (конечный) над алфавитом {a , b }.

3. Множество
является языком над алфавитом {a , b }. Этот язык бесконечный, он содержит слова b , ba , aba , baa , abaa , baaa , aabaa , abaaa и т.д.

Поскольку каждый язык является множеством, можно рассматривать операции объединения, пересечения и разности языков, заданных над одним и тем же алфавитом. Так, язык
, где
, называется дополнением языкаL относительно алфавита А . И если  всегда включено в А *, то язык
может как содержать, так и не содержать его. В последнем случае
.

Пусть ,
. Тогда языкназываетсяконкатенацией (сцеплением , произведением ) языков и . При этом
,
(n раз), если n >0.

Примеры . 1. Если
,
,то .

2. Если L={0, 01}, то
.

Итерацией языка L называется язык
(эта операция называется также звездочкой Клини ). Язык
называется позитивной итерацией языка L .

Пример . Если A ={a , b } и L ={aa , ab , ba , bb }, то
.

Обращением или зеркальным образом слова w называется слово w R , в котором буквы слова w идут в обратном порядке. Например, если w =bac , то

Пусть
. Тогда язык
называетсяобращением языка L .

Всякое начало слова будем называть префиксом , а всякий конец слова – суффиксом . Например, если y =xv , то х – префикс слова у (обозначение – х [y ), а v – суффикс слова у (обозначение – v ]y ). Очевидно, что пустое слово является как префиксом, так и суффиксом любого слова. Все префиксы слов языка
формируютмножество префиксов этого языка: Pref(L )
. АналогичноSuf(L )
-м ножество суффиксов языка
.

Если язык L таков, что никакое слово L не является префиксом (суффиксом) никакого другого слова L , то говорят, что L обладает префиксным (суффиксным) свойством .

Пусть А 1 и А 2 – алфавиты. Если отображение f :
удовлетворяет условиюдля всех слов
и
, то отображениеf называется гомоморфизмом .

Замечания. 1. Можно доказать, что если f – гомоморфизм, то
.

2. Гомоморфизмы не всегда являются биекциями, но каждый гомоморфизм однозначно определяется своими значениями на однобуквенных словах.

3. Применяя гомоморфизм к языку L , получаем другой язык f (L ).

Если f :
– гомоморфизм,
и
, то черезf (L 1) обозначается язык
, а через
обозначается язык
, а само отображение
называетсяобращением гомоморфизма .

Примеры . 1. Допустим, мы хотим заменить каждое вхождение в цепочку символа 0 на символ а , а каждое вхождение 1 – на bb . Тогда можно определить гомоморфизм f так, что
и
. Если
, то
.

2. Пусть f – гомоморфизм, для которого
и
. Тогда
и
.

Лабораторная работа №3

Разработка лексического анализатора выполняется достаточно просто, если используется теория регулярных языков и конечных автоматов. Рамках этой теории классы однотипных лексем рассматриваются как формальные языки (язык идентификаторов, язык констант и т.д.), множество предложений которых описывается с помощью соответствующей порождающей грамматики. При этом языки эти настолько просты, что они порождаются простейшей из грамматик – регулярной грамматикой.

Определение 1 . порождающая грамматика G = , правила которой имеют вид: А::=аВ или С::=b, где А, В,С Є N; a, b Є Т называется регулярной (автоматной).

Язык L (G), порождаемый автоматной грамматикой, называется автоматным (регулярным) языком или языком с конечным числом состояний.

Пример 1 . Класс идентификаторов, если идентификатором является последовательность, состоящая из букв и цифр, и первым символом идентификатора может быть только буква, описывается следующей порождающей регулярной грамматикой G = , в которой

N= {I, K}, T = {б, ц}, S={I},

P = { 1. I::= б

Здесь б, ц – обобщенные терминальные символы для обозначения букв и цифр соответственно.

Процесс порождения идентификатора «ббцбц» описывается следующей последовательностью подстановок

I => бК => ббК => ббцК => ббцбК => ббцбц

Однако основной задачей ЛА является не порождение лексических единиц, а их распознавание. Математической моделью процесса распознавания регулярного языка является вычислительное устройство, которое называется конечным автоматом (КА). Термин «конечный» подчеркивает то, что вычислительное устройство имеет фиксированный и конечный объем памяти и обрабатывает последовательность входных символов, принадлежащих некоторому конечному множеству. Существуют различные типы КА, если функцией выхода КА (результатом работы) является лишь указание на то, допустима или нет входная последовательность символов, такой КА называют конечным распознавателем.

Определение 2. Конечным автоматом называется следующая пятерка:

А = , где V = {a 1 , a 2 , …, a m } – входной алфавит (конечное множество символов);

Q = {q 0 , q 1 , …, q n -1 } – алфавит состояний (конечное множество символов);

δ: Q ×V →Q – функция переходов;

q 0 Є Q – начальное состояние конечного автомата;

F Є Q – множество заключительных состояний.

Схема функционирования КА.

Имеется бесконечная лента, разбитая на ячейки, в каждой из которых может находиться один символ из V. На ленте записана цепочка α Є V*. Ячейки слева и справа от цепочки не заполнены. Имеется конечное устройство управления (УУ) с читающей головкой, которое может последовательно считывать символы с ленты, передвигаясь вдоль ленты слева направо. При этом, УУ может находиться в каком – либо одном состоянии из Q. Начинает свою работу УУ всегда в начальном состоянии q 0 , а завершает в одном из заключительных состояний F. Каждый раз, переходя к новой ячейке на ленте, УУ переходит в новое состояние в соответствии с функцией δ.

Функцию переходов КА можно представить следующими способами:

· Совокупность команд;

· Диаграмма состояний;

· Таблица переходов.

Команда конечного автомата записывается следующим образом:

(q i , a j) → q k , где q i , q k Є Q; a j Є V.

Данная команда обозначает, что конечный автомат находится в состоянии q i , читает с ленты символ а j и переходит в состояние q k .

Графически команда представляется в виде дуги графа, идущей из вершины q i в вершину q k и помеченной символом a j входного алфавита:

Графическое представление всего отображения δ называют диаграммой состояний конечного автомата.

Если КА оказывается в ситуации (q i , a j), которая не является левой частью какой – либо команды, то он останавливается. Если же УУ считает все символы цепочки α, записанной на ленте, и при этом перейдет в заключительное состояние q r Є F, то говорят, что цепочка α допускается конечным автоматом.

Таблица переходов КА строится следующим образом: столбцы матрицы соответствуют символам из входного алфавита, строки – символам из алфавита состояний, а элементы матрицы соответствуют состояниям, в которые переходит КА для данной комбинации входного символа и символа состояния.

Пусть задана регулярная грамматика G = , правила которой имеют вид: А i::= a j A k или А i::= a j , где А i , A k Є N и a j Є Т.

Тогда конечный автомат А = , допускающий тот же самый язык, что порождает регулярная грамматика G, строится следующим образом:

2) Q = N U {Z}, Z N и Z T, Z – заключительное состояние КА;

5) Отображение δ строится в виде:

· Каждому правилу подстановки в грамматике G вида А i::= a j A k ставится в соответствие команда (А i , a j) → A k ;

· Каждому правилу подстановки вида А i::= a j ставится в соответствие команда (А i , a j) → Z;

Пример 2. Построить КА для грамматики из примера 1. Имеем А = , где

1) V = T = {б, ц}

2) Q = N U {Z} = {I, R, Z}

3) q 0 = {S} = {I}

5) δ: a) в виде совокупности команд:

б) в виде диаграммы состояний

Различают детерминированные и недетерминированные конечные автоматы. КА называется недетерминированным КА (НКА), если в диаграмме его состояний из одной вершины исходит несколько дуг с одинаковыми пометками. Например, КА из примера 2 является НКА.

Для практических целей необходимо, чтобы конечный распознаватель сам определял момент окончания входной последовательности символов с выдачей сообщения о правильности или ошибочности входной цепочки. Для этих целей входная цепочка считается ограниченной справа концевым маркером ├ и в диаграмму состояний КА вводятся интерпретированные состояния:

Z – «допустить входную цепочку»;

О – «запомнена ошибка во входной цепочке»;

Е – «отвергнуть входную цепочку».

Состояния Z и Е являются заключительными, и в них КА переходит при прочтении концевого маркера ├ соответственно после обработки правильной или ошибочной входной цепочки. Состояние О является промежуточным, в него КА переходит из любого допустимого состояния КА при обнаружении ошибки во входной цепочке и остается в нем до поступления концевого маркера ├, после чего осуществляется переход в состояние Е – «отвергнуть входную цепочку».