Теория абстрактных автоматов

Июль 21, 2022

Главная
Информатика
Теория абстрактных автоматов

Содержание

2. Распознающие автоматы
3. Автоматы и распознаваемые языки С точки зрения информатики совершенно все равно, из чего сделан автомат. Важно
4. Автоматы и распознаваемые языки Например, если команд только две, то их можно обозначить буквами, скажем, a
5. Автоматы и распознаваемые языки Автомат можно описать и другой информационной моделью — орграфом. Вершинами орграфа являются
7. Автоматы и распознаваемые языки Одно из состояний называется начальным — именно в нем находится автомат до
8. Автоматы и распознаваемые языки Ясно, что целью управления автоматом является выдача ему такой последовательности команд, которая
9. Автоматы и распознаваемые языки Множество всех тех слов, которые переводят автомат из начального состояния в одно
10. Недетерминированный автомат
11. Недетерминированный автомат Давайте, однако, предоставим автомату некоторую свободу. Пусть он уже не будет обязан однозначно реагировать
13. Недетерминированный автомат Как обычно, в нем одно состояние называют начальным; мы по-прежнему будем обозначать его q1.
14. Недетерминированный автомат А может и вообще перевести его в какое-нибудь промежуточное состояние. Например, слово bаb может
15. Недетерминированный автомат Разумеется, всякий (обычный) автомат естественно рассматривать как частный случай недетерминированного автомата. Поэтому множество распознаваемых
16. Недетерминированный автомат Два автомата (неважно, будут ли они недетерминированными или обычными) называть эквивалентными, если распознаваемые ими
17. Недетерминированный автомат Два автомата (неважно, будут ли они недетерминированными или обычными) можно называть эквивалентными, если распознаваемые
18. Приведение автоматов к детерминированному виду (Детерминированные конечные автоматы)
19. Детерминированные конечные автоматы Детерминированный конечный автомат имеет для любого входного символа не более одного перехода из
20. Детерминированные конечные автоматы Другими словами, эквивалентные автоматы реализуют одинаковые преобразования, но могут иметь различное число внутренних
21. Декомпозиция конечных автоматов
22. Декомпозиция конечных автоматов Декомпозиция автоматов — это представление конечного автомата в виде композиции нескольких автоматов. Возникающие
23. Декомпозиция конечных автоматов В связи с различными понятиями композиции задачу А можно ставить по-разному. Можно рассматривать
24. Декомпозиция конечных автоматов Например, если такие автоматы имеют: - меньшее число состояний, - меньше входных каналов,
25. Декомпозиция конечных автоматов Для уточнения постановки задачи введем понятие моделирования. Привлекая аналогии из алгебры, можно определить,
26. Декомпозиция конечных автоматов В теории автоматов интересуются главным образом поведением «вход-выход» автомата. Эквивалентными считаются два автомата,
27. Базис конечных автоматов Проблема полноты автоматного базиса
28. Базис конечных автоматов Набор структурных автоматов {A1,… Ar} называется полным (или базисом конечных автоматов), если из
29. Проблема полноты автоматного базиса В настоящее время существуют четыре основных подхода к задаче о полноте автоматного
30. Проблема полноты автоматного базиса Проблема полноты с учетом недостижимых состояний является алгоритмически неразрешимой. Эта проблема является
31. Контрольные вопросы Что называют абстрактным автоматом? Абстрактный автомат представляем собой множество из шести элементов. Назовите их.
33. Скачать презентацию

Слайд 2

Распознающие автоматы

Слайд 3

Автоматы и распознаваемые языки
С точки зрения информатики совершенно все равно, из

чего сделан автомат.
Важно лишь то, что он воспринимает некоторые сигналы как команды и по каждой команде выполняет некоторое действие, переходя из одного состояния в другое.
Поэтому можно считать, что каждый автомат описывается:
- набором возможных состояний,
- списком допустимых команд,
- перечислением того, из какого состояния в какое переходит автомат под воздействием каждой команды.

Слайд 4

Автоматы и распознаваемые языки
Например, если команд только две, то их можно

обозначить буквами, скажем, a и b, или цифрами, состояния автомата — буквами q1, q2, ..., qm,
а перечислить варианты перехода из одного состояния в другое можно с помощью таблицы (см. табл. 1).
В клетке, стоящей на пересечении строки и столбца, указывается то состояние, в которое переходит автомат, находившийся в состоянии, которое указано в заголовке того же столбца, и получивший команду, указанную в заголовке той же строки.

Слайд 5

Автоматы и распознаваемые языки
Автомат можно описать и другой информационной моделью —

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

Слайд 6

Слайд 7

Автоматы и распознаваемые языки
Одно из состояний называется начальным — именно в

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

Слайд 8

Автоматы и распознаваемые языки
Ясно, что целью управления автоматом является выдача ему

такой последовательности команд, которая переводит его из начального состояния в какое-либо конечное.
Поскольку каждая команда обозначена буквой, то набор команд, понимаемых данным автоматом, можно считать некоторым алфавитом А.
Тогда последовательность команд, т.е. программа, будет записываться как слово в этом алфавите.
Например, слово abа переводит автомат, описанный табл. 1, из начального состояния q1 в состояние q4.
Можно сказать, что слово abа задает на орграфе данного автомата некоторый маршрут из состояния q1 в состояние q4.

Слайд 9

Автоматы и распознаваемые языки
Множество всех тех слов, которые переводят автомат из

начального состояния в одно из конечных состояний, образует некий формальный язык.
Этот язык называется языком, распознаваемым данным автоматом.
Если для некоторого языка существует хотя бы один автомат, который этот язык распознает, то такой язык называют распознаваемым.

Слайд 10

Недетерминированный автомат

Слайд 11

Недетерминированный автомат
Давайте, однако, предоставим автомату некоторую свободу.
Пусть он уже не

будет обязан однозначно реагировать на каждую команду, а может по той или иной команде переходить в какое-нибудь из состояний, или вообще не менять состояние.
Конечно, мы по-прежнему можем изображать такой автомат размеченным орграфом, только теперь стрелок с одним и тем же символом алфавита, выходящих из одной вершины, может быть несколько или ни одной (см. рис. 2).
Такой автомат называют недетерминированным.

Слайд 12

Слайд 13

Недетерминированный автомат
Как обычно, в нем одно состояние называют начальным; мы по-прежнему

будем обозначать его q1.
Одно или несколько состояний являются конечными.
Цель та же — перевести последовательностью команд автомат из начального состояния в какое-нибудь конечное.
Как и ранее, языком, распознаваемым данным недетерминированным автоматом, называется множество слов, для каждого из которых существует хотя бы один путь, переводящий автомат из начального состояния в какое-либо конечное состояние.
Отличие, однако, в том, что теперь слово (т.е. последовательность команд) вовсе не каждый раз переведет автомат из начального состояния в то же самое конечное.

Слайд 14

Недетерминированный автомат
А может и вообще перевести его в какое-нибудь промежуточное состояние.

Например, слово bаb может перевести автомат, изображенный на рис. 2, из состояния q1 как в состояние q1, так и в состояние q3.
Можно сказать, что недетерминированный автомат до определенной степени моделирует поведение человека — одни и те же слова могут приводить к разным реакциям, а иногда и просто к «зависанию».

Слайд 15

Недетерминированный автомат
Разумеется, всякий (обычный) автомат естественно рассматривать как частный случай недетерминированного

автомата.
Поэтому множество распознаваемых языков содержится в множестве всех языков, распознаваемых недетерминированными автоматами.
Удивительно, что верно и обратное утверждение: всякий язык, распознаваемый каким-либо недетерминированным автоматом, является распознаваемым.

Слайд 16

Недетерминированный автомат
Два автомата (неважно, будут ли они недетерминированными или обычными) называть

эквивалентными, если распознаваемые ими языки совпадают.
Естественно для заданного распознаваемого языка интересоваться минимальным автоматом среди всех автоматов, распознающих данный язык.
Надо сказать, математики весьма преуспели в исследовании этого вопроса.

Слайд 17

Недетерминированный автомат
Два автомата (неважно, будут ли они недетерминированными или обычными) можно

называть эквивалентными, если распознаваемые ими языки совпадают.
Естественно для заданного распознаваемого языка интересоваться минимальным автоматом среди всех автоматов, распознающих данный язык.
Надо сказать, математики весьма преуспели в исследовании этого вопроса.

Слайд 18

Приведение автоматов к детерминированному виду (Детерминированные конечные автоматы)

Слайд 19

Детерминированные конечные автоматы
Детерминированный конечный автомат имеет для любого входного символа не

более одного перехода из каждого состояния.
Если для представления функции переходов используется таблица, то каждая запись в ней представляет собой единственное состояние.
Состояния q автомата М и q' автомата М' считаются эквивалентными, если оба автомата, получив одну и ту же (любую) входную последовательность символов, перерабатывают ее в одинаковую выходную последовательность.
Автоматы М и М' называются эквивалентными, если для каждого состояния автомата М существует эквивалентное ему состояние автомата М' и наоборот.

Слайд 20

Детерминированные конечные автоматы
Другими словами, эквивалентные автоматы реализуют одинаковые преобразования, но могут

иметь различное число внутренних состояний.
Понятие эквивалентности состояний применимо и к одному автомату (формально можно считать, что М и М' совпадают).
Для одного автомата эквивалентными будут различные состояния, через которые одна и та же входная последовательность символов преобразуется в одинаковую выходную.

Слайд 21

Декомпозиция конечных автоматов

Слайд 22

Декомпозиция конечных автоматов
Декомпозиция автоматов — это представление конечного автомата в виде

композиции нескольких автоматов.
Возникающие здесь проблемы являются типичными для структурной теории автоматов и вместе с тем они аналогичны проблемам, возникающим в современной алгебре.
Такие проблемы возникают, когда рассматривается представление данной алгебраической системы в виде нескольких более простых систем того же вида.

Слайд 23

Декомпозиция конечных автоматов
В связи с различными понятиями композиции задачу А можно

ставить по-разному.
Можно рассматривать представление автоматов в виде:
- прямой суммы,
- произведения,
- параллельно-последовательного соединения и т. п.
Представляет интерес прежде всего тот случай, когда автоматы, составляющие композицию, являются в некотором смысле более простыми, чем исходный автомат.

Слайд 24

Декомпозиция конечных автоматов
Например, если такие автоматы имеют:
- меньшее число

состояний,
- меньше входных каналов,
- если их функция переходов в некотором смысле более простая, и т. п.
Следовательно, задача А допускает много вариаций.

Слайд 25

Декомпозиция конечных автоматов
Для уточнения постановки задачи введем понятие моделирования.
Привлекая аналогии

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

Слайд 26

Декомпозиция конечных автоматов
В теории автоматов интересуются главным образом поведением «вход-выход» автомата.

Эквивалентными считаются два автомата, имеющие одинаковое поведение (но, возможно, различное число состояний).
Тогда естественно определить, что автомат А моделирует автомат В, если его поведение, с точностью до переименования входных и выходных букв, совпадает с поведением автомата В.
Или точнее, автомат А моделирует автомат В в том и только том случае, когда В является гомоморфным образом некоторого подавтомата автомата А.
Это называется моделирование 2-го рода.

Слайд 27

Базис конечных автоматов Проблема полноты автоматного базиса

Слайд 28

Базис конечных автоматов
Набор структурных автоматов {A1,… Ar} называется полным (или базисом

конечных автоматов), если из них можно построить любой наперед заданный структурный автомат.
В 1964 г. М.И. Кратко доказал несуществование алгоритма для определения полноты системы.
Под полнотой понимают выразимость всех функций через заданные.
Под выразимостью понимается возможность получения функций одного множества через функции другого с помощью заданных операций.

Слайд 29

Проблема полноты автоматного базиса
В настоящее время существуют четыре основных подхода к

задаче о полноте автоматного базиса.
Первый подход связан с расширением понятия равенства автоматов и их множеств.
Возникли дополнительные понятия полноты автоматного базиса.
Второй подход связан с вариацией операций, применяемых к автоматам.
Третий подход связан с изучением полноты в подклассах автоматов.
Четвертый подход связан с ограничением на исследуемые системы автоматов.

Слайд 30

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

неразрешимой.
Эта проблема является темой для многих научных диссертаций, поэтому далее углубляться в решение этих задач мы не будем.

Слайд 31

Контрольные вопросы
Что называют абстрактным автоматом? Абстрактный автомат представляем собой множество из

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

Теория абстрактных автоматов

Содержание

Распознающие автоматы

Автоматы и распознаваемые языкиС точки зрения информатики совершенно все равно, из

Автоматы и распознаваемые языкиНапример, если команд только две, то их можно

Автоматы и распознаваемые языкиАвтомат можно описать и другой информационной моделью —

Автоматы и распознаваемые языкиОдно из состояний называется начальным — именно в

Автоматы и распознаваемые языкиЯсно, что целью управления автоматом является выдача ему

Автоматы и распознаваемые языкиМножество всех тех слов, которые переводят автомат из

Недетерминированный автомат

Недетерминированный автоматДавайте, однако, предоставим автомату некоторую свободу. Пусть он уже не

Недетерминированный автоматКак обычно, в нем одно состояние называют начальным; мы по-прежнему

Недетерминированный автоматА может и вообще перевести его в какое-нибудь промежуточное состояние.

Недетерминированный автоматРазумеется, всякий (обычный) автомат естественно рассматривать как частный случай недетерминированного

Недетерминированный автоматДва автомата (неважно, будут ли они недетерминированными или обычными) называть

Недетерминированный автоматДва автомата (неважно, будут ли они недетерминированными или обычными) можно

Приведение автоматов к детерминированному виду (Детерминированные конечные автоматы)

Детерминированные конечные автоматыДетерминированный конечный автомат имеет для любого входного символа не

Детерминированные конечные автоматыДругими словами, эквивалентные автоматы реализуют одинаковые преобразования, но могут