Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
ДИСКРЕТНАЯ МАТЕМАТИКА
Содержание
- 1. ДИСКРЕТНАЯ МАТЕМАТИКА
- 2. Слайд 2
- 3. С.130-134,134 -143
- 4. ДМ 2. Теория формальных языков и автоматов.Тема
- 5. Т7.Автоматы, и формальные языки
- 6. Регулярные языки и конечные автоматы
- 7. Множество всех слов, распознаваемых автоматом, мы назвали языком.
- 8. Автоматный языкГрамматика типа 3 – имеют правила
- 9. Суммой языков L и L´ называется язык,
- 10. Далее конкатенацией (или соединением) слов w и
- 11. Произведением языков L и L´ называется
- 12. Итерацией языка L называется язык, который обозначается
- 13. Пусть имеется алфавит А = {а1, а2, …, аs}.
- 14. Регулярным языком называется такой язык, который можно
- 15. Пусть автомат с начальным состоянием v1
- 16. ТЕОРЕМА КЛИНИ (основная теорема теории автоматов). Язык
- 17. Stephen C Kleene-1909-1994. США.
- 18. Хомский, Аврам Ноам
- 19. Это теоретическая основа многих информационных технологий, таких
- 20. Понятие о задании автоматасетью Петри
- 21. Начальное состояние — маркировка 100; возбуждены переходы t1 и t2.
- 22. Матричное задание СП
- 23. Если срабатывает t1, то фишка забирается из р1 и передается в р2.
- 24. Получаем маркировку 010, возбужден только переход t3;
- 25. Если срабатывает t2, то фишки появляются в
- 26. Если срабатывает t4, то сеть возвращается к начальной маркировке
- 27. срабатывание t3 приводит к маркировке 101.
- 28. Магазинный автомат
- 29. Магазин - стекСтек (англ. stack — стопка)
- 30. Стек
- 31. Стеки широко используются в вычислительной технике —
- 32. Языки программирования высокого уровня используют стек вызовов для передачи параметров при вызове процедур.
- 33. Стек FIFOFirst In First Out
- 34. Лекция 13
- 35. Эквивалентность автоматов. Теорема Мура
- 36. Автоматы А и В
- 37. Их реакции на входную цепочку aabbabb одинаковы:
- 38. Эквиваленты ли эти автоматы? Перебрать все входные цепочки невозможно – их бесконечно много.
- 39. Поэтому проблема эквивалентности автоматов нетривиальна.К счастью, существует
- 40. Теорема Мура.
- 41. Теорема Мура. Два конечных автоматас одинаковым входным
- 42. Два конечных автомата с одинаковым входнымалфавитом эквивалентны
- 43. Параллельно работающие на одном входе автоматы
- 44. Граф прямого произведения автоматов А и В - автомат А × В
- 45. Удалим недостижимые состояния
- 46. Видно, что для каждого состояния выполняется выдача
- 47. Минимизация автоматов
- 48. Минимизация конечных автоматовРазные автоматы могут функционировать одинаково,
- 49. Слайд 49
- 50. Начальное разбиение – это один блок, включающий все состояния: 0= {А0 }.
- 51. Строим 1 – те состояния, которые
- 52. Слайд 52
- 53. Теперь смотрим, в какие блоки переходит автомат
- 54. Итак, в первой строчке под воздействием «а»
- 55. Во второй строчке под воздействием «а» осуществляется
- 56. В третьей строчке под воздействием «а» осуществляется
- 57. В четвёртой строчке под воздействием «а» осуществляется
- 58. Получили π2 = {А2 = ;В2=; С2=; D2=}.
- 59. Строим π3. При его построении уже не
- 60. Получаем разбиение π3= {А3 = ; В3=;
- 61. Строим π4
- 62. Получаем разбиениеπ4= {А4 = ; В4=; С4=;
- 63. Слайд 63
- 64. Рассмотрим особенности нахождения классов эквивалентности для автомата Мили
- 65. Первый шагНаходясь в состояниях 1, 2, 3
- 66. Поэтому на первом этапе множество состояний V
- 67. Второй шагКласс В1 не разбивается, т.к. из состояний
- 68. Второй шагКласс А1 разбивается по символу а
- 69. Второй шагПоэтому группа состояний 1, 3 и
- 70. Второй шагТаким образом, по окончании второго этапа получаем разбиение на три класса: 2={А2 = ; В2 = ; С2 = }.
- 71. М =< К,Σ,π,s,F,S,ε >K — конечное множество
- 72. Таким образом, функция перехода является отображением То
- 73. Слайд 73
- 74. Слайд 74
- 75. Скачать презентанцию
С.130-134,134 -143
Слайды и текст этой презентации
Слайд 4ДМ 2. Теория формальных языков и автоматов.
Тема 4. Логические автоматы
Тема
5.Тестирование логических автоматов
формальные языки
Слайд 8Автоматный язык
Грамматика типа 3 – имеют правила вида АaB, либо
Ab, где А,ВN; a,bT.
Здесь A,B,a,b – одиночные символы (не цепочки)
соответствующих словарей.A,B - состояния автомата, a,b - входные символы
Слайд 9Суммой языков L и L´ называется язык, который обозначается L + L´
и получается объединением множеств L и L´, т.е.
L + L´ =
Сумма языков состоит
из слов, принадлежащих хотя бы одному из языков L и L´. Поэтому L + L´ = L´ + L ..
Слайд 10Далее конкатенацией (или соединением) слов w и w´ будем называть
слово ww´, полученное приписываем справа слова w´ к слову w.
Например, конкатенацией слов ba и cba будет слово bacba.
Из этих же слов можно получить слово cbaba, которое является конкатенацией cba и ba.
В общем случае конкатенации ww´ и w´w различаются.
.
Слайд 11 Произведением языков L и L´ называется язык, который обозначается
L·L´ и получается в результате конкатенации всех возможных слов w
и w´, где w принадлежит языку L, а w´ – языку L´,Пример 1. Пусть L = {a, cb}, L´ = {ab, bсb}. Тогда
L·L´ = {aab, abcb, cbab, cbbcb},
L´·L = {aba, abcb, bcba, bcbcb}.
Слово abcb принадлежит обоим языкам L·L´ и L´·L.
Слайд 12Итерацией языка L называется язык, который обозначается L* и получается
в результате сложения бесконечного числа языков
Слайд 13Пусть имеется алфавит
А = {а1, а2, …, аs}. Одноэлементные языки а1,
а2, …, аs, а также язык, содержащий только пустое слово
Λ, будем называть элементарными языками.
Слайд 14Регулярным языком называется такой язык, который можно получить из элементарных
языков с помощью конечного числа операций сложения, умножения и итерации.
Слайд 15 Пусть автомат с начальным состоянием v1 и заключительным состоянием
v3 задан графом
Язык L можно задать регулярным выражением
b·(a + b)*
+ a·b*·а·(a + b)*
Слайд 16ТЕОРЕМА КЛИНИ (основная теорема теории автоматов).
Язык L распознается конечным
детерминированным автоматом тогда и только тогда, когда L – регулярный
язык.
Слайд 19Это теоретическая основа многих информационных технологий, таких как разработка математического
обеспечения вычислительных систем, проектирование компиляторов и синтаксических анализаторов для языков
программирования, создание лингвистических структур для баз данных и знаний
Слайд 24Получаем маркировку 010, возбужден только переход t3; после его срабатывания
сеть возвращается к начальной маркировке 100.
Слайд 25Если срабатывает t2, то фишки появляются в р2 и р3.
Получаем маркировку 011, при которой возбуждены переходы t3 и t4,
каждый из которых может сработать.
Слайд 29Магазин - стек
Стек (англ. stack — стопка) — структура данных
с методом доступа к элементам LIFO (англ. Last In —
First Out, «последним пришел — первым вышел»).Стек - магазин - по аналогии с магазином в огнестрельном оружии (стрельба начнётся с патрона, заряженного последним
Слайд 31Стеки широко используются в вычислительной технике — так для отслеживания
точек возврата из подпрограмм стек вызовов, который является неотъемлемой частью
архитектуры большинства современных процессоров.
Слайд 32
Языки программирования высокого уровня используют стек вызовов для передачи параметров
при вызове процедур.
Слайд 38Эквиваленты ли эти автоматы?
Перебрать все входные цепочки невозможно –
их бесконечно много.
Слайд 39Поэтому проблема эквивалентности автоматов нетривиальна.
К счастью, существует метод решения этой
проблемы.
Он основан на понятии прямого произведения автоматов.
Слайд 41Теорема Мура.
Два конечных автомата
с одинаковым входным
алфавитом эквивалентны
тогда и только тогда, когда для любого достижимого состояния в
их прямом произведении А × В функции выходов одинаковы:
Слайд 42Два конечных автомата
с одинаковым входным
алфавитом эквивалентны тогда и только
тогда, когда для любого достижимого состояния в их прямом произведении
А × В функции выходов одинаковы:
Слайд 46Видно, что для каждого состояния выполняется выдача пар одинаковых выходных
сигналов. Следовательно, автоматы А и В эквивалентны.
Слайд 48Минимизация конечных автоматов
Разные автоматы могут функционировать одинаково, даже если у
них разное число состояний.
Важной задачей теории автоматов является нахождение минимального
автомата, реализующего заданное автоматное отображение.
Слайд 51Строим 1 – те состояния, которые не различаются цепочкой
длины 1 – то есть символом либо а, либо b.
Видим,
что состояния разбиваются на два блока – в первом реакции 1,0, во втором – 0,1: 1= {А1=<1,3,5,6,8,9>;В1=<2,4,7>}
Слайд 53Теперь смотрим, в какие блоки переходит автомат из блоков
1 под воздействием символов а, либо b.
Слайд 54Итак, в первой строчке под воздействием «а» осуществляется переход в
состояние 3 – это блок А1, под воздействием «b» осуществляется
переход в состояние 6, это тоже блок А1. Так и записываем. π 1=
{А1 = <1,3,5,6,8,9>;
В1=<2,4,7>}.
Слайд 55Во второй строчке под воздействием «а» осуществляется переход в состояние
4 – это блок В1, под воздействием «b» осуществляется переход
в состояние 6, это блок А1. π 1=
{А1 = <1,3,5,6,8,9>;
В1=<2,4,7>}.
Слайд 56В третьей строчке под воздействием «а» осуществляется переход в состояние
1 – это блок А1, под воздействием «b» осуществляется переход
в состояние 4, это блок В1. π 1=
{А1 = <1,3,5,6,8,9>;
В1=<2,4,7>}.
Слайд 57В четвёртой строчке под воздействием «а» осуществляется переход в состояние
7 – это блок В1, под воздействием «b» осуществляется переход
в состояние 9, это блок А1. Действуя аналогично, получаем всю таблицуπ 1=
{А1 = <1,3,5,6,8,9>;
В1=<2,4,7>}.
Слайд 59Строим π3. При его построении уже не нужно анализировать, в
какой блок π2 переходит автомат из состояния 8, поскольку оно
единственное в π2 и дальше дробиться не будет.π2 = {А2 = <1,5,6>;
В2=<2,4,7>;
С2=<3,9>;
D2=<8>}.
Слайд 62Получаем разбиение
π4= {А4 = ; В4=; С4=; D 4=; Е4=}.
Поскольку
π4 = π3, искомое разбиение найдено.
Минимальный автомат имеет 5 состояний,
а его функции переходов и выходов определяются так (берём за основу разбиение π3):(А3,а)= D3, ψ (А3,а)=1 и так далее.
Слайд 65Первый шаг
Находясь в состояниях 1, 2, 3 и 6, автомат
преобразует входной символ a в выходной символ a, а в
состояниях 4 и 5 преобразует а в b.По входному символу b классы А1 и В1 не разбиваются.
Слайд 66Поэтому на первом этапе множество состояний V расщепляется по входному
символу а на два класса:
1 А1 = {1, 2, 3, 6} и
В1 = {4, 5}. 
Слайд 67Второй шаг
Класс В1 не разбивается, т.к. из состояний 4 и 5
под действием входного сигнала а автомат переходит в состояния 6
и 3, которые принадлежат одному классу А1, а под действием сигнала b – в состояние 1, которое тоже принадлежат классу А1.
Слайд 68Второй шаг
Класс А1 разбивается по символу а на два класса:
А2 = {1, 3, 6} и В2 = {2}. Действительно, под действием входного символа
а из состояний 1, 3 и 6 автомат переходит в состояния 2 и 1, которые принадлежат классу А1, а из состояния 2 – в состояние 5, которое классу А1 не принадлежит.
Слайд 69Второй шаг
Поэтому группа состояний 1, 3 и 6 после разбиения
класса А1 не может попасть в один новый класс вместе
с состоянием 2.Класс А2 далее не разбивается, поскольку под действием символа b автомат из состояний 1, 3 и 6 попадает в состояния 5 и 4, которые принадлежат одному классу C2.
Слайд 70Второй шаг
Таким образом, по окончании второго этапа получаем разбиение на
три класса:
2={А2 = ; В2 = ; С2 = }.
Слайд 71М =< К,Σ,π,s,F,S,ε >
K — конечное множество состояний автомата;
Σ —
допустимый входной алфавит, из которого формируются строки, считываемые автоматом;
s— единственно
допустимое начальное состояние автомата; π -функция переходов из состояний в другие состояния;
F— множество конечных состояний, причём допустимо F=Ø, и F=K,
S — алфавит памяти (магазина),
ε— нулевой символ памяти.
Память работает как стек, то есть для чтения доступен последний записанный в неё элемент
Слайд 72Таким образом, функция перехода является отображением
То есть, по комбинации
текущего состояния, входного символа и символа на вершине магазина автомат
выбирает следующее состояние и, возможно, символ для записи в магазин.В случае, когда в правой части автоматного правила присутствует ε, в магазин ничего не добавляется, а элемент с вершины стирается.
Если магазин пуст, то срабатывают правила с ε в левой части.
