shpory_diskra (Шпоры к экзамену по дискретке, вопросник внутри (лектор Иванов А.О., ИУ8)), страница 2

Вопрос №29

Вопрос №30

Вопрос №31

Вопрос №32

М Матрица смежности вершин – это квадратная матрица B n-го порядка, элементы которой определяются для неориентированного графа следую­щим образом: b_ij={^{1, если из i-ой вершины в j-ую ведет дуга,}_{0, иначе}. Заме­чание: в k-ой строке матрицы орграфа количество еди­ниц равно полустепени исхода dg⁺v_k вершины v_k, а коли­чество единиц в k-ом столбце – полустепени захода dg^-v_k. Матрица достижимости – это матрица C размера |V||V|, каждый элемент которой C_ij={^{1, если j-я вершина достижима из I-й,}_{0, иначе}. Согласно определению достижимости, эле­менты C_ij=1. Матрица достижимости несет очень важную информацию о графе. C для любой пары индексов i, j C_ij=C_ji=1, дает номера вершин, образующих бикомпо­ненту, а для любых i, j C_ij=1 или C_ij=1, дает номера вер­шин, образующих компоненту. Элемент a^<l>_ij матрицы меток дуг A^l, l0 равен стоимости прохождения из i в j по всем путям длины l. Т.к. стоимость прохождения ме­жду парой вершин <v_i,v_j> равна сумме меток всех путей, ведущих из первой вершины во вторую, а указанную сумму можно получить, суммируя последовательно метки путей длины 0, длины 1, длины 2 и т.д., то мат­рица стоимостей взвешенного орграфа может быть представлена в виде C=A⁰+A¹+A²+Aⁿ+…=_n0Aⁿ или C=A*. Матрица меток дуг, размеченная над булевым полукольцом B=({0,1}, +, , 0, 1) – матрица смежности. Решая в B=({0,1}, +, , 0, 1) систему уравнений при всех j=1..n: =A+_j , где _j – j-й единичный вектор, получаем наименьшее решение вида =A*_j. Тогда столбец =A*_j есть j-й столбец матрицы достижимости С=A*.

Задачу о кратчайших расстояниях можно сформулировать так. Пусть задан взвешенный ориентированный граф и пусть из вершины v достижима вершина w. Фиксируем какой-либо путь S, ведущий из v в w. Расстоянием от вершины v до вершины w по пути S называют сумму меток дуг, входящих в этот путь, а наименьшим — минимальное из расстояний между вершинами v и w по всем возможным путям.

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

Матрица стоимостей ориентированного графа G, размеченного над полукольцом с итерацией R (в частности, над замкнутым полукольцом), равна итерации матрицы A меток дуг ориентированного графа G.

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовём соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещённую и повторим шаг алгоритма.

Алгоритм поиска в глубину

Вход. Граф G=(V,E), заданный списками смежности.

Выход. Множества Tree древесных и Back обратных ребер соответственно; множество Fc фундаментальных циклов, массив D, содержащий D-номера вершин.

0. Просмотреть массив лидеров и сформировать множество V0 вершин графа. Это множество используется для хранения новых (не обработанных алгоритмом) вершин. В ходе работы алгоритма обработанные вершины будут удаляться из этого множества.

В процессе работы алгоритма для каждой вершины v необходимо знать, какие вершины из ее списка смежности L[v] обработаны на предыдущих шагах работы алгоритма. Для этого формируется массив Lp размера |V0|, в котором хранятся номера первых еще не обработанных алгоритмом вершин списка смежности L[v] каждой вершины v. Первоначально все элементы массива Lp полагают равными 1.

Стек вершин STACK и список вершин фундаментального цикла Cycle положить пустыми (STACK=∅, Cycle=∅).

Множества Tree древесных ребер, Back обратных ребер и Fc фундаментальных циклов положить пустыми (Tree=∅, Back=∅,Fc=∅). Массив D-номеров D обнулить.

Задать начальную вершину для поиска (v=v0). (Обычно это первая вершина массива лидеров.) Счетчик D-номеров вершин count положить равным 1 (count=1).

1. Если множество V0 не пусто (V0≠∅), перейти на шаг 2, если иначе — на шаг 8 (выход).

2. Если стек пуст (STACK=∅) и алгоритм стартует из вершины v0 (count=1), то перейти на шаг 3, если иначе, то выбрать из множества V0 произвольную вершину, из которой поиск в глубину будет продолжен (v=u,u∈V0), и перейти на шаг 3.

3. Поместить текущую вершину v в стек STACK. Присвоить вершине v D-номер (D[v]=count). Увеличить счетчик D-номеров на 1 (count=count+1). Удалить вершину v из множества V0 новых вершин. Перейти на шаг 4.

4. Проверить по элементу Lp[v], что не достигнут конец списка смежности L[v] текущей вершины v. Если в списке смежности есть еще не обработанные вершины, получить из списка смежности очередную вершину w, увеличить Lp[v] на 1 и перейти на шаг 6.

Если список смежности L[v] вершины v обработан полностью, удалить вершину v из стека STACK и перейти на шаг 5.

5. Если стек STACK пуст, вернуться на шаг 1, если иначе, то в качестве текущей вершины v взять вершину, находящуюся в вершине стека, и перейти на шаг 4.

6. Если вершина w новая (w∈V0), то добавить ребро {v,w} в множество древесных ребер

Tree=Tree∪{{v,w}},

сделать вершину w текущей (v=w) и вернуться на шаг 3. Если вершина w не новая (w∉V0), то перейти на шаг 7.

7. Если ребра {v,w} нет среди древесных ({v,e}∉Tree), поместить ребро в список обратных ребер

Back=Back∪{{v,w}},

Поместить вершину w в список Cycle. Читать содержимое стека STACK, начиная с вершины стека, до появления вершины w и помещать в список Cycle (включая вершину w), т.е. формировать фундаментальный цикл, соответствующий обратному ребру {v,w}.

Добавить список Cycle в множество фундаментальных циклов Fc

Fc=Fc∪{Cycle}.

Список Cycle положить пустым (Cycle=∅).

Вернуться на шаг 4.

8. Закончить работу.

Вопрос №33

Вопрос №34

Вопрос №35

Вопрос №36

Поиск в ширину рассматриваем только для ориентированного графа.

Вход. Граф G=(V,E), заданный списками смежности; v0 — начальная вершина (не обязательно первый элемент массива лидеров).

Выход. Массив M меток вершин, где каждая метка равна длине пути от v0 до v.

0. Очередь Q положить пустой (Q=∅). Все вершины пометить как недостижимые из вершины v0, присваивая элементам массива M значение +∞ (M[vi]=+∞, i=1..N).

Стартовую вершину v0 пометить номером 0, т.е. длину пути от стартовой вершины v0 до самой себя положить равной 0 (M[v0]=0). Поместить вершину v0 в очередь Q. Перейти на шаг 1.

1. Если очередь Q не пуста (Q≠∅), то из "головы" очереди извлечь (с удалением из очереди) вершину u и перейти на шаг 2. Если очередь пуста, перейти на шаг 3.

2. Если список смежности L(u) вершины u пуст, вернуться на шаг 1.

Если список смежности L(u) вершины и не пуст, для каждой вершины w из списка смежности, где M[w]=+∞, т.е. вершины, которую еще не посещали, положить длину пути из стартовой вершины v0 до вершины w равной длине пути от v0 до вершины u плюс одна дуга (L[w]=M[u]+1), т.е. отметить вершину w и поместить ее в очередь Q. После просмотра всех вершин списка смежности L(u) вернуться на шаг 1.

3. Распечатать массив M. Закончить работу.

Алфавит – произвольное непустое конечное множество V={a₁ ,…,a_n }, элементы которого называют буквами или символами.

Словом или цепочкой в алфавите V называют произвольный кортеж из множества V^К (К-ой декартовой степени алфавита V) для различных К=0, 1, … .

Длина слова – число компонент кортежа.

Языком в алфавите V называется произвольное подмножество множества V*.

Множество всех языков в алфавите V, т.е. 2 ^V*, есть булеан счетного множества и имеет мощность континуума.

Операции над языками:

Соединение (конкатенация) слов: для х=х(1) х(2)… и у= у(1) у(2)… соединение ху = х=х(1) х(2)…у(1) у(2)… . Из определения следует, что конкатенация ассоциативна и множество V* всех слов в алфавите V образует моноид. Конкатенация языков L₁ и L₂ – язык L₁L₂, состоящий из всех возможных соединений слов ху, где слово хL₁, а yL₂ .

Итерация языка L - объединение всех его степеней. L* = Lⁿ, где n = 0….

L(V)=(2V∗,∪,⋅,∅,{λ})

Регулярные операции-операции объединения,соединения,итерации.

L₁+L₂,L₁*L₂,L₁*-рег. языки в V.

В замкнутом полукольце L(V) всех языков в алфавите V рассмотрим подалгебру, порожденную множеством, которое состоит из пустого языка, языка {λ}, всех языков {a}, a∈V (каждый из которых содержит единственную однобуквенную цепочку a), и замкнутую относительно итерации. Эта подалгебра, обозначаемая R(V), есть полукольцо с итерацией. Оно играет важнейшую роль в теории формальных языков. Его называют полукольцом регулярных языков.

Рег языки:

1) пустое множество ∅, множество {λ} (состоящее из одной пустой цепочки) и множество {a} для каждого a∈V считаем регулярным языком в алфавите V;

2) если известно, что P и Q — регулярные языки в алфавите V, то к множеству регулярных языков в алфавите V следует добавить объединение P∪Q и соединение PQ;

3) если известно, что P — регулярный язык в алфавите V, то к множеству регулярных языков в алфавите V следует добавить его итерацию P∗;

4) никаких других регулярных языков, кроме определенных в пунктах 1-3, не существует.

Мощность множества регулярных языков равна 2^V .

рег языки - см вопрос 35

Вопрос №37

Вопрос №38

Вопрос №39

Вопрос №40

рег языки и автоматы распозн - 35: 36 вопр
Задача построения языка по автомату. Для решения этой задачи достаточно любым методом вычислить матрицу стоимости автомата (напр., решить в полукольце R(V) систему уравнений =A+, где -столбец, компоненты которого равны , кроме тех, которые соответствуют заключ. состояниям).

Лемма о разрастании: Если L – регулярный язык, то существует N(L) : для любой цепочки xL, длина кото­рой  N, х допускает представление в виде х=u v w, где v и |v|N, причем для n0 цепочка х_n=u vⁿ w L. Иначе говоря, эта лемма утверждает, что любой регу­лярный язык допускает представление всех своих дос­таточно длинных цепочек в виде соединения трех цепо­чек, причем средняя их них не пуста, ограничена по длине и ее итерация не приводит к выбросу за пределы языка. Доказательство: Т.к. язык регулярен, следова­тельно существует конечный автомат, реализующий его. Положив N=|Q|, фиксируем произвольную цепочку xL, длина которой  N, а т.к. N > 0, то x=x(0)…x(l). l>0. Т.к. автомат является КДА, то существует единственный путь ведущий из начального состояния в одно из конеч­ных на котором читается х. Т.к. длина цепочки х не меньше числа состояний М, т.е. числа всех вершин графа М, то, поскольку число вершин в любом пути на 1 больше числа дуг в этом пути, число вершин в рассмот­ренном пути будет больше, чем число всех вершин графа. Это значит, что хотя бы одна из вершин данного пути повторяется и она, т.обр. она содержится в некото­ром контуре. Тогда путь, несущий цепочку х, делится на 3 части: до контура, контур и после контура.

Пример нерегулярного языка: L={aⁿ bⁿ | n0}, к этому языку не применима лемма о разрастании. Дока­зательство: Выберем достаточно большое n и получим следующие варианты подцепочки v:

1. v=a^s , s<n; Очевидно, что это целиком выве­дет за пределы языка, т.к. число а, а b=const.

2. v=b^s , s<n; Аналогично.

3. v=a^p a^q , 0<p<n, 0<q<n; в данном случае возник­нет вхождение подцепочки ba, в слово, которое уже не принадлежит нашему языку. Следовательно, язык L не регулярен.

Лемма о разрастании: Если L – регулярный язык, то существует N(L) : для любой цепочки xL, длина кото­рой  N, х допускает представление в виде х=u v w, где v и |v|N, причем для n0 цепочка х_n=u vⁿ w L. Иначе говоря, эта лемма утверждает, что любой регу­лярный язык допускает представление всех своих дос­таточно длинных цепочек в виде соединения трех цепо­чек, причем средняя их них не пуста, ограничена по длине и ее итерация не приводит к выбросу за пределы языка. Доказательство: Т.к. язык регулярен, следова­тельно существует конечный автомат, реализующий его. Положив N=|Q|, фиксируем произвольную цепочку xL, длина которой  N, а т.к. N > 0, то x=x(0)…x(l). l>0. Т.к. автомат является КДА, то существует единственный путь ведущий из начального состояния в одно из конеч­ных на котором читается х. Т.к. длина цепочки х не меньше числа состояний М, т.е. числа всех вершин графа М, то, поскольку число вершин в любом пути на 1 больше числа дуг в этом пути, число вершин в рассмот­ренном пути будет больше, чем число всех вершин графа. Это значит, что хотя бы одна из вершин данного пути повторяется и она, т.обр. она содержится в некото­ром контуре. Тогда путь, несущий цепочку х, делится на 3 части: до контура, контур и после контура.

Пример нерегулярного языка: (Язык допускается КА тогда и только тогда, когда он порождается регулярной грамма­тикой). L={aⁿ bⁿ | n0}, к этому языку не применима лемма о разрастании. Доказательство: Выберем дос­таточно большое n и получим следующие варианты подцепочки v:

1. v=a^s , s<n; Очевидно, что это целиком выве­дет за пределы языка, т.к. число а, а b=const.

2. v=b^s , s<n; Аналогично.

v=a^p a^q , 0<p<n, 0<q<n; в данном случае возник­нет вхождение подцепочки ba, в слово, которое уже не принадлежит нашему языку. Следовательно, язык L не регулярен.

Конечный автомат – орграф, размеченный над полукольцом R(V) регулярных языков в алфавите V, с выделенной вершиной q₀ , которая называется начальной и ограниченным набором заключительных вершин.

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

Способы задания: граф, таблица.

Вопрос №41

Вопрос №42

Вопрос №43

Вопрос №44

Конечный автомат – орграф, размеченный над полукольцом R(V) регулярных языков в алфавите V, с выделенной вершиной q₀ , которая называется начальной и ограниченным набором заключительных вершин. Конечный автомат называется детерминированным, если в нем нет дуг с меткой  и из любого состояния по любому входному символу возможен переход ровно в одно состояние. Постановка задачи о минимизации. Существует автомат M. Существует ли автомат M’, который так же реагирует на входные последовательности, но имеет меньшее число состояний. Автомат называется минимальным, если его нельзя покрыть автоматом с меньшим числом состояний. Два состояния s₁ и s₂ E_r эквивалентны если для любого aA^r (s₁,a)= (s₂,a). Два состояния называются E эквивалентными, если они E_r эквивалентны для любого r. Теорема. Пусть задан автомат M. S’ – множество классов эквивалентности его состояний. S’ является множеством состояний автомата M’. M’ – минимальный автомат, эквивалентный M.

Грамматика G={X_T, X_N, A, M} ={терм.алфавит; нетерм. алф.; аксиома; множ. правил вывода или продукций} X_C=X_NX_Т

Порождающая грамматика является классическим способом определения языка. Порождающая грамматика позволяет выводить цепочки языка из некоторой начальной цепочки с помощью определенных правил замены. Процесс порождения – пошаговый. Язык, порождаемый грамматикой G – множество всех терминальных цепочек, выводимых из аксиомы грамматики. L(G)={xSx, xX_T*}

Вывод в грамматике: цепочка 0, 1, …,n, если  i-1; n- длина вывода; 0 – аксиома грамматики.

Иерархия Хомского. Согласно иерархии Хомского грамматики делятся на классы:

1. Грамматики 0 (грамматики общего вида) – никак не ограничены

2. Контекстные грамматики - 1А21  2 AX_n; 1 ,2, X_c*

3. Контекстно-свободные грамматики - А AX_n; X_c⁺

4. Линейные грамматики - Аа В с или Аа; A,BX_n; a,cX_T; если с=, то грамматика –праволинейная.

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

Конечный автомат – орграф, размеченный над полукольцом R(V) регулярных языков в алфавите V, с выделенной вершиной q₀ , которая называется начальной и ограниченным набором заключительных вершин.

Регулярные языки порождаются регулярными грамматиками, которые, будучи частным случаем праволинейных грамматик, являются «наименьшим» типом грамматик в иерархии Хомского.

Вопрос №45

Вопрос №46

Вопрос №47

НК-грамматики – неукорачивающие грамматики. G является НК-грамматикой, если для  ее продукции  длина ||||

Теорема: Для  НК-грамматики может быть построена эквивалентная ей контекстная грамматика.

Доказательство: 1А21  2, Требуется изменить систему продукции, не меняя языка.

Переопределим систему продукции:

X_N’=X_N{D1…Dn}

Составим следующую систему продукции.  - плохая грамматика. =xi1…xin; =xj1…xjn

Xi1…xinD1X12…x1n

D

…

D1…Dn-1XinD1…Dn-1x1n

D1…Dnxj1 D2…Dn

…

xj1…xjn-1Dnxj1…xjn=

Теперь для аX_T X_N’=X_N{E_a}, Во всех продукциях все терминалы заменены на нетерминалы, но наш язык пуст. Добавим продукции типа E_a а а. Мы получили К-грамматику, но язык не изменился.

В иерархии Хомского НК-грамматики – класс 1.

Задача распознавания в НК-грамматиках.

G.   X_T*. a, т.е. выводима ли  в G.

Теорема:  алгоритм, который по  НК-грамматике G и   X_T* решает задачу распознавания за конечное число ходов.

Доказательство: Есть G={X_T, X_N, A, M}. Если выводимо  G, то:

1. в выводе нет повторов

2. А01… n=, то   j 

К(n) – количество переходов X_G* длины  n |X_G|=q

К(n) = 1+q+…+qn=(qⁿ⁺¹-1/q-1)<qⁿ⁺¹

Выводов длины К не больше, чем К(n)! \

Выводов длины  К : К! +С_К^К-1(К-1)!+…+С_К¹ 1!, что меньше суммы К! от 0 до n. Значит выводов – конечное число.

Алгоритм:

По  ищем К()  |X_G|^||+1

Все выводы длины  К без повторов.

Строим дерево выводов.

Весь этот абзац, только если очень захочется:

Контекстно-свободными называются языки порожденные КС-грамматиками, т.е. такими грамматиками, для которых правило вывода следующее: Нетерминаллюбая цепочка в объединенном алфавите. КС языки не обязаны быть регулярными т.к. КС-грамматики являются более общими по сравнению с регулярными. Т.е. РЕГКС.

Доказательство существования нерегулярных КС языков. Приведем пример КС языка, не воспринимаемого КА:

G={X_T={a,b}, X_N={A₀}, A₀, ={A₀a b, A₀a A₀ b}} ; данная грамматика КС, но не регулярная.

L(G)={ aⁿ bⁿ | n>0 } – не регулярен в силу леммы о разрастании.