2.1.1 Определение и свойства регулярных выражений
Проблема генерирования бесконечных языков посредством конечных описаний решается различными способами. Одним из них является использование регулярных выражений для порождения бесконечных цепочек языка.
Регулярное множество и регулярное выражение для некоторого алфавита V определяется рекурсивно следующим образом:
Иными словами, регулярные множества – это цепочки символов над заданным алфавитом, построенные с использованием операций объединения, конкатенации и замыкания.
Все регулярные языки представляют собой регулярные множества.
Два регулярных выражения a и b эквивалентны: a = b , если они обозначают одно и то же множество.
Каждое регулярное выражение обозначает одно и только одно регулярное множество, но для одного регулярного множества может существовать сколько угодно задающих его регулярных выражений.
При записи регулярных выражений используются круглые скобки, как для обычных арифметических выражений. При отсутствии скобок операции выполняются слева направо с учетом приоритета. Наивысшим приоритетом обладает операция итерации, затем конкатенации, потом – объединение множеств.
Например, язык, представляющий собой множество всех цепочек из нулей и единиц произвольной длины, может быть описан эквивалентными регулярными выражениями α1 и α2: α1 = (0+1)*, α2 = (0*1*)*. α1 = α2 .
Пусть a , b , g – регулярные выражения. Тогда свойства регулярных выражений можно записать в виде следующих формул:
|
|
|
Все эти свойства доказываются с применением аппарата теории множеств, т.к. регулярные выражения – это обозначения для соответствующих множеств.
Простейшие уравнения с регулярными коэффициентами будут выглядеть следующим образом: X=a X+b ; X=Xa +b , где a ,b Î V* – регулярные выражения над алфавитом V, а XÏ V. Два вида записи уравнений (правосторонняя и левосторонняя запись) связаны с тем, что для регулярных выражений операция конкатенации не обладает свойством коммутативности. Обе записи равноправны.
Решениями таких уравнений будут регулярные множества. Это значит, что, если взять РМ, являющееся решением уравнения, обозначить его соответствующим РВ и подставить в уравнение, то получится тождественное равенство.
Решением первого уравнения является регулярное множество, обозначенное a *b. Если подставить его вместо переменной X в уравнение, получим a X+b =a (a *b)+b =6 (a a * )b +b =13(a a * )b +l b =5(a a * +l )b =1a * b =X.
Аналогично, для второго уравнения решение будет иметь вид b a *. Подставив его в уравнение, также получим тождество.
Указанные решения уравнений не всегда являются единственными. Например, если регулярное выражение a в первом уравнении обозначает множество, которое содержит пустую цепочку, то решением уравнения может быть любое множество, обозначенное выражением X=a *(b +g ), где g может обозначать произвольное множество (в том числе не регулярное). Однако указанные решения – наименьшие возможные для данных уравнений. Они называются наименьшей подвижной точкой.
Из рассмотренных уравнений можно формировать систему уравнений с регулярными коэффициентами. Например, в правосторонней записи такая система будет иметь вид:
В данной системе все коэффициенты a ij – регулярные выражения над алфавитом V, а переменные не входят в этот алфавит: XiÏ V " i.
Системы уравнений с регулярными коэффициентами решаются методом последовательных подстановок. Рассмотрим метод решения для правосторонней записи. Алгоритм работает с переменной номера шага i.
Алгоритм решения:
Система уравнений с регулярными коэффициентами всегда имеет решение, но оно не всегда единственно. Рассмотренный алгоритм всегда находит решение, которое является наименьшей подвижной точкой системы уравнений.
2.2.1 Автоматные грамматики
Среди регулярных грамматик можно выделить отдельный класс – автоматные грамматики. Они могут быть леволинейными и праволинейными.
Леволинейные автоматные грамматики G(VT, VN, P, S) могут иметь правила двух видов: A ® Bt или A ® t, где A, BÎ VN, tÎ VT.
Праволинейные автоматные грамматики могут тоже иметь правила двух видов: A ® tB или A ® t, где A,BÎ VN, tÎ VT.
Классы обычных регулярных грамматик и автоматных почти эквивалентны (т.е. с точностью до правила S ® l ). В общем случае в автоматных грамматиках разрешается правило вида S ® l , где S – целевой символ грамматики, который не должен встречаться в правых частях других правил грамматики. Тогда язык, задаваемый автоматной грамматикой G, будет включать в себя пустую цепочку: l Î L(G). В таком случае классы регулярных и автоматных грамматик становятся эквивалентными.
Как следует из определения, в правилах автоматных грамматик в отличие от регулярных вместо цепочки терминальных символов присутствует только один терминальный символ. Любая автоматная грамматика является регулярной, обратное же справедливо не всегда.
Существует алгоритм, позволяющий преобразовать регулярную грамматику к автоматному виду. Он очень полезен, т.к. упрощает задачу построения распознавателей для регулярных языков. Кратко его идея состоит в том, что при наличии в правой части правила регулярной грамматики цепочки терминальных символов длины n необходимо ввести n–1 дополнительный нетерминальный символ и записать для каждого из них соответствующие правила, т.е. разбить стоящую справа терминальную цепочку на символы и разнести их по разным правилам.
Пример. Рассмотрим регулярную грамматику и приведём её к автоматному виду. G({0,1},{S,A},P,S), S ® 001A, A ® 0A | 1A | 11. Эта грамматика задаёт язык с алфавитом {0,1}, все цепочки которого начинаются с цепочки ‘001’, а заканчиваются цепочкой‘11’.
В первом правиле присутствует цепочка из трёх терминальных символов, значит, потребуется добавить два нетерминала. Пусть это будут B и C. Первое правило примет вид: S ® 0B, B ® 0C, C ® 1A. 2 правила для A останутся без изменения: A ® 0A | 1A, а третье правило A ® 11 тоже придётся разбить на два путём добавления ещё одного нетерминала, например, D: A ® 1D, D ® 1. Итак, теперь грамматика будет содержать 5 нетерминалов и 7 правил: G({0,1},{S,A,B,C,D},P,S), S ® 0B, B ® 0C, C ® 1A, A ® 0A | 1A | 1D, D ® 1.
С автоматной грамматикой тесно связано понятие конечного автомата. Автоматная грамматика позволяет сгенерировать все цепочки некоторого регулярного языка, а конечный автомат – распознать этот язык.
Конечным автоматом (КА) называют пятёрку следующего вида: M(Q,V,d ,q0,F), где
КА называется полностью определённым, если в каждом его состоянии существует функция переходов для всех возможных входных символов: " aÎ V, " qÎ Q $ d (q,a)={R, RÍ Q}.
Работа автомата представляет собой последовательность тактов (или шагов). На каждом шаге работы автомат может остаться в том же состоянии или перейти в другое. Поведение автомата на каждом такте определяется функцией переходов, которая зависит от текущего состояния и входного символа. Если функция переходов допускает несколько переходов в следующее состояние, то КА может перейти в любое из них, и такой КА является недетерминированным (НКА).
В начале работы автомат находится в начальном состоянии q0. Работа автомата продолжается до тех пор, пока на его вход поступают символы входной цепочки.
Мгновенным описанием (МО), или конфигурацией автомата M называется пара (q, w), где qÎ Q – состояние УУ, wÎ V* – неиспользованная часть входной цепочки (т.е. символ, обозреваемый считывающей головкой и все символы справа от него). Тогда пара (q0, w) называется начальной конфигурацией для цепочки w, а конфигурация (q, l ) является заключительной, или допускающей, если qÎ F (т.е. q – одно из заключительных состояний автомата).
Представим такт автомата M бинарным отношением ├─M на множестве конфигураций. Тогда: если d (q,a) содержит p: pÎ d (q,a), то для обозначения такта записывают (q,aw)├─M (p,w) для всех цепочек wÎ V*. Здесь q,pÎ Q, aÎ V, т.е. a является символом входного алфавита.
Рефлексивное и транзитивное замыкание отношения ├─ обозначается через ├─*.
Цепочка w допускается автоматом M, если (q0,w)├─*(q,l ) для некоторого qÎ F, т.е. получив на вход эту цепочку, автомат из начальной конфигурации может перейти в заключительную.
Язык, допускаемый (определяемый) автоматом M, представляет собой множество L(M)={w½ wÎ V* и $ qÎ F½ (q0,w)├─*(q,l )}. Два автомата эквивалентны, если они задают один и тот же язык.
Таким образом, из вышесказанного следует, что КА является распознавателем для формальных языков. Можно доказать, что он является распознавателем именно для регулярных языков.
Пусть M – конечный автомат. Он является детерминированным (ДКА) если множество d (q,a) содержит не более одного состояния " aÎ V, " qÎ Q. Если d (q,a) всегда содержит ровно одно состояние, то M является полностью определённым (ПО).
Функция переходов КА может быть задана таблицей или графом переходов (диаграммой).
В таблице принято в качестве заголовков строк брать состояния автомата, а в качестве заголовков столбцов – символы алфавита. Если в ячейке пересечения строки p и столбца a стоит состояние q, то это означает, что при прочтении символа a автомат переходит из состояния p в q. Тогда в случае детерминированного полностью определённого автомата в каждой ячейке таблицы будет находиться ровно одно состояние.
Граф переходов КА – это направленный помеченный граф, вершины которого обозначены состояниями автомата, а дуги – символами входного алфавита. При этом дуга (p,q)½ p,qÎ Q обозначена символом aÎ V, если в КА определена d (p,a) и qÎ d (p,a).
Начальное и конечное состояния на графе помечаются специальным образом, как правило, начальное – дополнительной пунктирной линией, а конечное – двойным кружком.
Для моделирования работы КА удобно, чтобы в нём были заданы все возможные переходы для всех символов входного алфавита. Если это не так, то автомат можно привести к полностью определённому виду путем ввода дополнительного состояния “ошибка”, на которое следует замкнуть все неопределённые переходы, а все переходы из этого нового состояния замкнуть на него же.
Рассмотрим два примера конечных автоматов – ДКА и НКА.
1. Пусть M=({p,q,r},{0,1},d ,p,{r}) – ДКА, где функция переходов задана таблицей:
вход |
Автомат M допускает все цепочки из {0,1}*, содержащие два стоящих рядом нуля. Попав в состояние r, автомат из него уже не выходит. Пусть w=’01001’. |
||
состояние |
0 |
1 |
|
p |
{q} |
{p} |
|
q |
{r} |
{p} |
|
r |
{r} |
{r} |
Рассмотрим последовательность тактов для данной цепочки w.
(p,01001) ├─ (q,1001) ├─ (p,001) ├─ (q,01) ├─ (r,1) ├─ (r,l ). Поскольку rÎ F, это означает, что ‘01001’Î L(M).
2. Построим НКА, допускающий цепочки в алфавите {1,2,3}, у которых последний символ цепочки уже появлялся в ней ранее (т.е., например, цепочка ‘1232’ должна быть допущена, а ‘122113’ – нет). Введем состояния: q0 – нейтральное, qi делает предположение, что последний символ цепочки совпадает с индексом состояния, qf – заключительное состояние. Из состояния q0 автомат может перейти в qa, если наблюдает символ ”a”, или остаться в q0. Находясь в qa и наблюдая символ ”a”, автомат может перейти в заключительное состояние qf или остаться в qa. Из qf автомат никуда не переходит.
Формально такой автомат определим следующим образом:
M=({q0,q1,q2,q3,qf},{1,2,3},d ,q0,{qf}), функция переходов задана таблицей:
вход |
Рассмотрим для примера цепочку w=’12321’. Процесс порождения конфигураций будет выглядеть следующим образом: |
|||
состояние |
1 |
2 |
3 |
|
q0 |
{q0,q1} |
{q0,q2} |
{q0,q3} |
|
q1 |
{q1,qf} |
{q1} |
{q1} |
|
q2 |
{q2} |
{q2,qf} |
{q2} |
|
q3 |
{q3} |
{q3} |
{q3,qf} |
|
qf |
Æ |
Æ |
Æ |
Поскольку (q0,12321)├─*(qf,l ), то ‘12321’Î L(M).
Моделировать работу ДКА значительно проще, чем НКА. Доказано, что для любого НКА можно построить эквивалентный ему ДКА. Для этого существует специальный алгоритм, идея которого состоит в следующем:
После построения ДКА из него удаляют все недостижимые состояния (состояния, переход в которые невозможен при любой входной цепочке).
В итоге построен ДКА, эквивалентный заданному НКА. При этом если исходный автомат имел n состояний, то в наихудшем случае построенный ДКА будет иметь (2n–1) состояний.
Рассмотрим на примере построение ДКА, эквивалентного заданному НКА.
1. Пусть M=({p,q,r},{0,1},d ,p,{r}) – НКА, где функция переходов d задана графом:
Недетерминированный автомат M допускает все цепочки из {0,1}*, заканчивающиеся двумя единицами: (0+1)*11. Представим функцию переходов в табличном виде (таблица справа). |
вход |
|||||
состояние |
0 |
1 |
||||
p |
{p} |
{p,q} |
||||
q |
– |
{r} |
||||
r |
– |
– |
||||
вход |
Далее создадим все возможные новые состояния, которые могут получиться в результате сочетаний исходных состояний, и занесём их в таблицу. Новые состояния будем записывать в виде {pq}. Тогда из состояния p по символу 1 переход будет происходить в такое состояние pq. В таблице присутствуют недостижимые состояния q, r, pr и qr, которые можно удалить без изменения результата. |
|||||
состояние |
0 |
1 |
||||
p |
{p} |
{pq} |
||||
q |
– |
{r} |
||||
r |
– |
– |
||||
pq |
{p} |
{pqr} |
||||
pr |
{p} |
{pq} |
||||
qr |
– |
{r} |
||||
pqr |
{p} |
{pqr} |
Можно было упростить процесс и сразу заносить в новую таблицу только те состояния, которые действительно могут возникнуть. Тогда состояния pr и qr в ней бы не появились. После удаления недостижимых состояний таблица примет вид:
вход |
Для удобства переобозначим состояния: заменим p на A, pq на B, pqr – на C. Тогда начальным состоянием будет A, конечным C. |
вход |
||||
состояние |
0 |
1 |
состояние |
0 |
1 |
|
p |
{p} |
{pq} |
A |
{A} |
{B} |
|
pq |
{p} |
{pqr} |
B |
{A} |
{C} |
|
pqr |
{p} |
{pqr} |
C |
{A} |
{C} |
В итоге полученный детерминированный автомат, эквивалентный исходному НКА, будет иметь вид: M=({A,B,C},{0,1},d ,A,{C}), граф функции переходов d :
Многие КА возможно минимизировать, т.е. построить эквивалентный КА с минимально возможным числом состояний. Для этого существует алгоритм минимизации автомата. Дадим необходимые определения.
Пусть q1 и q2 – состояния автомата M, на вход подается цепочка символов w длины k³ 0: wÎ V*, ½ w½ £ k, (q1,w) ├─* (q3,l ), (q2,w) ├─* (q4,l ). Если одно из состояний (q3 или q4) входит в F, а другое – нет, то говорят, что цепочка w различает состояния q1 и q2. Если же для любой входной цепочки w длины k она не различает состояния q1 и q2, то говорят, что они являются k-эквивалентными или k-неразличимыми. Множество K-эквивалентных состояний составляет класс эквивалентности R(k).
Очевидно, что множества F и Q\F являются 0-эквивалентными, записывается этот факт следующим образом: R(0)={F,Q\F}.
Для построения минимального автомата строятся классы эквивалентности R(n). Алгоритм построения классов эквивалентности:
Алгоритм минимизации автомата:
Рассмотрим пример. Пусть ДКА имеет вид: M = ({q0, q1, q2, q3, q4, q5}, {0,1}, d , q0, {q4, q5}), а функция переходов задана графом:
Требуется минимизировать данный автомат.
Недостижимых состояний нет. Построим классы эквивалентности: R(0)={{q0,q1,q2,q3}, {q4,q5}}. Из состояния q2 по 0 происходит переход в q3, а из q1 – в q4. Состояния q3 и q4 находятся в разных классах эквивалентности R(0) Þ q1 и q2 будут входить в разные классы R(1). Аналогично рассуждая про остальные состояния, получим: R(1)={{q4,q5},{q0,q2},{q1,q3}}. Аналогично: R(2)={{q4,q5}, {q0,q2}, {q1,q3}}. Þ В новом автомате 3 состояния. Обозначим их по номеру одного из состояний каждого класса. M’ = {q0,q1,q4}, {0,1}, d ’, q0, {q4}).
вход |
Выясните, какой язык задаётся данным автоматом. Доопределите автомат до полностью определённого вида. |
||
состояние |
0 |
1 |
|
p |
{q} |
– |
|
q |
{r} |
{r} |
|
r |
{q} |
{q} |
2.3.1 Способы задания регулярных языков
Регулярные грамматики, конечные автоматы и регулярные множества (и обозначающие их регулярные выражения) представляют собой три различных способа задания регулярных языков.
Утверждение
Все эти три способа эквивалентны. Существуют алгоритмы, позволяющие для языка, заданного одним из способов, построить другой способ, определяющий этот же язык (см. список литературы).
Например, для нахождения регулярного выражения для языка, заданного праволинейной грамматикой, необходимо построить и решить систему уравнений с регулярными коэффициентами.
В теории языков программирования наиболее важную роль играет эквивалентность КА и регулярных грамматик, поскольку такие грамматики используются для определения лексических конструкций языков программирования. Создав на основе известной грамматики автомат, получаем распознаватель для данного языка. Таким образом удается решить задачу разбора для лексических конструкций языка.
Для построения КА на основе известной регулярной грамматики её необходимо привести к автоматному виду. Множество состояний автомата будет соответствовать множеству нетерминальных символов грамматики.
Регулярные множества замкнуты относительно операций пересечения, объединения, дополнения, итерации, конкатенации, изменения имен символов и подстановки цепочек вместо символов.
Для регулярных языков разрешимы многие проблемы, неразрешимые для других типов языков. Например, следующие проблемы являются разрешимыми независимо от того, каким из способов задан язык:
Проблема эквивалентности: Даны два регулярных языка L1(V) и L2(V). Необходимо установить, являются ли они эквивалентными.
Проблема принадлежности цепочки языку. Дан регулярный язык L(V), цепочка символов a Î V*. Требуется проверить, принадлежит ли эта цепочка языку.
Проблема пустоты языка. Дан регулярный язык L(V). Необходимо проверить, является ли этот язык пустым, т.е. найти хотя бы одну цепочку a ¹ l , a Î L(V).
Иногда бывает необходимо доказать, является ли некоторый язык регулярным. Если возможно задать этот язык одним из рассмотренных способов, то он является регулярным. Но если такой способ найти не удается, неизвестно, является язык регулярным или нет.
Для регулярных языков выполняется т.н. лемма о разрастании регулярных языков. Она часто используется для доказательства (от противного) того факта, что некоторый язык не является регулярным. Для такого доказательства предполагают, что язык является регулярным, в таком случае лемма должна выполняться. Если в результате получается противоречие, это доказывает, что предположение было неверным, следовательно, язык регулярным не является.
Лемма о разрастании регулярных языков формулируется следующим образом. Если дан регулярный язык и достаточно длинная цепочка символов, принадлежащая этому языку, то в ней можно найти непустую подцепочку, которую можно повторить сколь угодно много раз, и все полученные таким образом цепочки также будут принадлежать рассматриваемому регулярному языку.
Формально лемма записывается так. Если дан регулярный язык L, то $ константа p>0, такая, что если a Î L и ½ a ½ ³ p, то цепочку a можно записать в виде a = d b g , где 0<½ b ½ £ p, и тогда a ¢ =d b ig , a ¢ Î L " i³ 0.
Пример. Рассмотрим язык L={anbn½ n>0}. Докажем, что он не является регулярным, используя для этого лемму о разрастании языков.
Пусть этот язык регулярный, тогда для него должна выполняться лемма о разрастании. Возьмем некоторую цепочку этого языка a = anbn и запишем ее в виде a = d b g . Если b Î a+ или b Î b+, то тогда цепочка d b ig не принадлежит языку для любого i, что противоречит условиям леммы. Если же b Î a+b+, то цепочка d b 2g также не принадлежит языку L. Получили противоречие, следовательно, язык не является регулярным.
2.3.3 Контрольные вопросы