PP_s14 (1076815)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

РЕГУЛЯРНЫЕ ЯЗЫКИ ИКОНЕЧНЫЕ АВТОМАТЫ• 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.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов семинаров