PP_s14 (Семинары)

РЕГУЛЯРНЫЕ ЯЗЫКИ ИКОНЕЧНЫЕ АВТОМАТЫ• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit1. Алфавит, слово, языкАлфавит — это произвольное непустое конечное множествоV = {a1, . . . , an}, элементы которого называют буквами, илисимволами.Определение 6.1. Словом, или цепочкой, в алфавите V называют произвольный кортеж из множества V k ( k -ой декартовойстепени алфавита V ) для различных k = 0, 1, 2, . . .Например, если V = {a, b, c}, то (a), (b), (c), (a, b), (a, b, c),(c, b, a, a, c) и т.

д. есть слова в V.При k = 0 получаем пустой кортеж, называемый в данном контексте пустым словом, или пустой цепочкой и обозначаемый λ.Множество всех слов в алфавите V обозначают V ∗, а множество всехнепустых слов в V — V +. Слова будем записывать без угловых скобок и запятых. Так, для записанных выше слов получим: a, b, c, ab,abc, cbaac.Пустое слово λ — это слово, не имеющее символов.Длину слова w можно понимать как число составляющих это словобукв.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitОпределение 6.2.

Языком в алфавите V называется произвольное подмножество множества V ∗.Поскольку языки есть множества слов, к языкам применимы теоретикомножественные операции ∪ , ∩ , , 4 ,и т.д.Определение 6.3. Соединением языков L1 и L2 называют языкL1L2, состоящий из всех возможных соединений слов xy, в которыхслово x принадлежит первому, а слово y — второму языку, т.е.L1L2 = {xy|x ∈ L1 и y ∈ L2}.Пример 1.

Если V = {a, b, c}, L1 = {ab, bcc, cab}, L2 = {ca, bcc},тоL1L2 = {abca, abbcc, bccca, bccbcc, cabca, cabbcc}.Формально можно записать:(ab + bcc + cab)(ca + bcc) = abca + abbcc + bccca + bccbcc + cabca + cabbcc.Соединение языков не коммутативно. Например,L2L1 = {caab, cabcc, cacab, bccab, bccbcc, bcccab} =6 L 1 L2 .• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitОперация соединения языков позволяет определить операцию возведенияязыка в произвольную натуральную степень: для любого L ⊆ V ∗L0 = {λ}, а для любого n > 0 Ln = Ln−1L.Итерацией языка L называют объединение всех его степеней:∞[L∗ =Ln .n=0Рассматривая объединение всех степений языка L, начиная с первой,получим позитивную итерацию+L =∞[Ln .n=1Основное алгебраическое свойство множества всех языков в алфавите Vсформулировано в следующей теореме.Теорема 1.

Алгебра∗L(V ) = (2V , ∪, ·, ∅, {λ})есть замкнутое полукольцо.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitВ замкнутом полукольце L(V ) всех языков в алфавите V рассмотрим подалгебру, порожденную множеством, состоящим из пустогоязыка, языка {λ} и всех однобуквенных языков {a}, a ∈ V, и замкнутую относительно итерации. Эта подалгебра, обозначаемая R(V ),является полукольцом с итерацией.Элементы полукольца R(V ) называются регулярными множествами, или регулярными языками.Определение 6.4. Пусть фиксирован некоторый алфавит V. Тогда:1) Пустое множество ∅, множество {λ} (состоящее из одной пустойцепочки ) и множество {a} для каждого a ∈ V является регулярнымязыком (множеством) в алфавите V.2) Если P и Q — регулярные языки в алфавите V, то объединениеP ∪ Q и соединение P Q — регулярные языки в алфавите V.3) Если P — регулярный язык в алфавите V, то итерация P ∗ —регулярный язык в алфавите V.4) Никаких других регулярных языков, кроме определенных в пп.

(1) —(3), не существует.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitАлгебраические операции над регулярными множествами удобно представлять с помощью так называемых регулярных выражений.Каждое регулярное выражение представляет (или обозначает) некоторое однозначно определяемое регулярное множество, причем:1) регулярные выражения ∅, λ и a обозначают регулярные множества ∅, {λ} и {a} соответственно (a ∈ V ) ;2) если регулярное выражение p обозначает регулярное множество P,а q обозначает Q, то регулярные выражения (p + q), (pq) и (p∗)обозначают регулярные множества P ∪ Q, P Q и P ∗ соответственно.Для регулярного выражения αα∗ или α∗α будем использовать обозначение α+ и называть это выражение позитивной итерацией выраженияα.• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit2.

Вычисление языка, допускаемого КАОпределение 6.5. Конечный автомат — это орграф, размеченный над полукольцом R(V ) регулярных языков в алфавите V, свыделенной вершиной q0, которая называется начальной и выделенным подмножеством вершин F, каждый элемент которого называетсязаключительной вершиной.На функцию разметки при этом накладываются следующие ограничения: метка каждой дуги есть либо язык {λ}, либо непустое подмножество алфавита V .Вершины графа называют обычно в этом случае состояниями конечного автомата, начальную вершину — начальным состоянием, заключительную вершину — заключительным состояниемконечного автомата.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЕсли e = (q, r) — дуга автомата M, и ее метка ϕ(e) есть регулярноевыражение λ, то в этом случае будем говорить, что в автомате Mвозможен переход из состояния q в состояние r по пустойцепочке и писать q →λ r.

Дугу с меткой λ будем называть λ переходом ( или пустой дугой).Если же метка дуги e есть множество, содержащее входной символa, то будем говорить, что в автомате M возможен переход изсостояния q в состояние r по символу a и писать q →a r.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitСогласно общему определению метки пути в размеченном орграфеметка пути в конечном автомате есть соединениеметок входящихв этот путь дуг (в порядке их прохождения).

Таким образом, меткалюбого пути конечной длины в конечном автомате есть регулярныйязык.Если цепочка x ∈ ϕ(W ), где W — некоторый путь, ведущий извершины q в вершину r конечного автомата M, то говорят, чтоцепочка x читается на пути W в M . Пишем q ⇒∗x r , если xчитается на некотором пути из q в r.Стоимость прохождения из состояния q в состояние r есть(согласно общему определению этого понятия в размеченных орграфах)объединение меток всех путей, ведущих из q в r, т.

е. множество всехтаких x, что q ⇒∗x r.Язык L(M ) конечного автомата M есть множество всех цепочекво входном алфавите, читаемых в M на некотором пути из начальногосостояния в какое-либо из заключительных.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitЧтобы найти язык конечного автомата, надо вычислить сумму техэлементов матрицы стоимостей автомата, которые находятся на пересечении строки, соответствующей начальному состоянию q0 и в столбцов,соответствующих всем заключительным состояниям qf ∈ F.Чтобы практически вычислить язык конечного автомата, достаточнорешить систему уравненийξ = Aξ + β,(1)где A - квадратная матрица n -ого порядка, элемент aij которой естьрегулярное выражение, служащее меткой дуги из вершины (состояния)qi в вершину (состояние) qj , если такая дуга существует, и естьрегулярное выражение ∅ , если нет дуги из qi в qj ;β — столбец, компоненты с номерами t1, .

. . , tm, , соответствующихзаключительным состояниям, равны единице полукольца ( λ ), а всеостальные компоненты равны нулю полукольца ( ∅ ).(Ко всем уравнениям системы, соответствующим заключительнымсостояниям, добавляется слагаемое λ. )• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitРешение системы (1) будет иметь вид:∅ ...

 ∅  λ  t1 ∅∗∗  .. ξ=Aβ=A  . ∅ λ t  m∅ .  .. ∅(2)(элементы λ находятся в строках с номерами t1, . . . , tm ). Умножая в (2)матрицу A∗, равную матрице C стоимостей, на столбец β, получимстолбец, s -я компонента которого xs будет равна произведению s -ойстроки матрицы C (cs1, . . . , cst1 , . . .

, cstm , . . . csn) на столбец β , т.е.xs = cst1 + . . . + cstm ,Полученное регулярное выражение описывает язык конечного автомата.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitРис. 1Пример 2. Найдем язык конечного автомата, изображенного нарис. 1. Запишем для этого автомата систему уравнений:x0 = ax1 + bx2,x1 = bx0 + ax1,x2 = ax0 + bx1 + λ,Cлагаемое λ добавлено в уравнение для x2 , так как вершина q2является заключительной.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitИсключая x0 , получимx1 = b(ax1 + bx2) + ax1,x2 = a(ax1 + bx2) + bx1 + λ.ОтсюдаТогдаx1 = (ba + a)∗b2x2,x2 = (a2 + b)(ba + a)∗b2x2 + abx2 + λ.x2 = ((a2 + b)(ba + a)∗b2 + ab)∗,x1 = (ba + a)∗b2((a2 + b)(ba + a)∗b2 + ab)∗.Отсюда получаем регулярное выражение, обозначающее язык КА, какзначение переменной x0 :x0 = a(ba + a)∗b2((a2 + b)(ba + a)∗b2 + ab)∗++ b((a2 + b)(ba + a)∗b2 + ab)∗.Полученное регулярное выражение достаточно сложно, и найти его, нерасполагая заранее разработанным алгоритмом, было бы затруднительно.• First • Prev • Next • Last • Go Back • Full Screen • Close • QuitРис.

2b, cb a,a, b $ a,'λ? - q1 - q2 - q1- q2 a 6b, c6 c c??b%qq3 3a, b % Задачи6.1. Доказать, что язык L+k=∞[Li регулярен для любого k при условииi=k>0регулярности L .6.2. Привести примеры слов в алфавите {a, b, c} , которые задаются следующими регулярными выражениями:(а) (a + b)∗ c∗ (b + c) ;(б) ((ab)+ (ca)∗ )∗ ;(в) (a+ (b + c)∗ a + b+ (a + b)∗ bc)∗ ;6.3. Найти языки, допускаемые конечными автоматами, заданными на рис.2.• First • Prev • Next • Last • Go Back • Full Screen • Close • Quit6.4. Найти язык, допускаемый конечным автоматом:(а) вход: q1 ; выходы: q2 , q3 ; дуги: (q1 , q2 , a) , (q1 , q4 , a, b) , (q2 , q4 , a, b) ,(q3 , q4 , λ) , (q4 , q3 , a, b) , (q3 , q2 , a, b) , (q4 , q2 , b) ;(б) входы: q0 , q1 ; выходы: q2 , q1 ; дуги: (q0 ,q2 ,a,b,c) , (q0 ,q1 ,a) , (q1 ,q0 ,a,b) ,(q1 , q2 , a, c) , (q2 ,q0 ,c) , (q2 ,q2 ,a,b) .6.5.