Синтез автомата по регулярным выражениям.
Основные правила
- итерация
- усеченая итерация
Приоритеты выполнения операций
1. 
2. 
3. 
Любые отступления от этого порядка выполнения операций обозначаются путем введения круглых скобок.
Для описания регулярных событий будем пользоваться системой основных событий, т.е. некоторыми стандартными заготовками.
1. Событие, состоящее из всех слов входного алфавита, называется универсальным (всеобщим) и имеет вид
2. Событие, включающее все возможные слова, состоящие из букв: 
, например 
3. Событие, содержащее все слова, оканчивающиеся буквой 
4. Событие, содержащее все слова, оканчивающиеся отрезком слова 
5. Событие, состоящее из всех слов, имеющих начальный и конечный отрезки l1 и l2 соответственно
6. Событие, содержащее все слова, в которых хотя бы один раз встречается отрезок l1 в любом месте
7. Событие, содержащее только одно-буквенные слова входного алфавита
8. Событие, содержащее только двух-буквенные слова входного алфавита
9. Событие, содержащее все слова из букв входного алфавита длины n
10. Событие, содержащее все слова из букв входного алфавита длины кратной n
11. Событие, состоящее из всех слов, которые начинаются буквами xi или xk
12. Событие, состоящее из всех слов алфавита 
, не содержащее комбинации букв 
и оканчивающееся на буквой 
13. Событие, состоящее из всех слов алфавита , не содержащее комбинации букв 
и оканчивающееся на буквой
|
|
|
14. Событие, состоящее из всех слов алфавита , не содержащее серии из r букв 
и оканчивающееся на буквой
Пример 1. Записать событие, состоящее из всех слов алфавита 
, которые начинаются буквой 
или 
, а заканчиваются отрезком 
Решение: используя п.п. 11, 1, 4 получим 
Пример 2. Составить регулярные выражения для автомата А, сравнивающего два двоичных числа. Количество разрядов в числах произвольно. Окончание чисел фиксируется буквой 
. Сравниваемые числа имеют одинаковое количество разрядов. Числа подаются на вход начиная с младших разрядов.
Если 1-е число < 2-го, то А выдает сигнал y1, 
Если 1-е число > 2-го, то А выдает сигнал y2, 
Если 1-е число = 2-e, то А выдает сигнал y3, 
Решение: На вход поступают пары двоичных цифр 00, 01, 10, 11. Первая цифра относится к 1-му числу, вторая – ко 2-му. Эти комбинации можно закодировать как 
, тогда входным алфавитом будет 
Регулярные выражения будут описывать все условия "если".
1.) Событие, которое отражает равенство входных цифр, а также и чисел – сигнал y3, , и по условию должно заканчиваться буквой .
2.) Событие для сингала y1, будет содержать все слова, в которых после произвольной комбинации букв обязательно следует буква , т.е. 
. После сигнала/буквы на вход автомата могут поступать только одинаковые комбинации, т.е. 
или 
, т.е. 
. Окончание сравниваемых чисел обозначается буквой .
|
|
|
При объединении данных рассуждений в единое регулярное выражение, получим:
3.) Рассуждения для записи события, соответствующего сигналу y2, аналогичны п.2.
Для проверки сравним числа 
Получено следующее выражение: 
До 7 разряда следует произвольная комбинация букв , т.е. 
, в 7 разряде находится буква , а затем следуют токо одинаковые комбинации, т.е. буквы или . Таким образом получаем, что первое число меньше второго, т.е.
Пример 3. Составить регулярные выражения для автомата, выполняющего функции дешифратора. На вход дешифратора поступают 3-х разрядные двоичные числа. После подачи цифры старшего разряда дешифратор выдает один из сигналов 
, в зависимости от того, какое из чисел 
поступило на вход дешифратора.
Решение: Цифры 0 и 1 3-х разрядных двоичных чисел поступают на вход последовательно, пусть 
- соответствует поступлению на вход 0, - поступление 1, поэтому входной алфавит 
. Использование 0 и 1 во входном алфавите для последующей записи регулярных выражений может привести к путанице и сокращению булевых выражений, что делать в данном случае нельзя, т.е. 
.
|
|
|
До подачи на вход автомата какого-либо 3-разрядного числа, могли поступать другие 3-х разрядные числа, таким образом 
- событие, описывающее, что было до поступления на вход автомата конкретной комбинации, т.е. могла прийти любая 3х-буквенная комбинация.
Когда поступила конкретная комбинация, РВ будут иметь вид:
Пример 4. Составить регулярные выражения для следующего автомата А. На вход А поступают 4х-разрядные двоичные числа – тетрады. Тетрады являются правильными, если они меньше 10, остальные – неправильные. При поступлении на вход автомата любой правильной тетрады на выходе формируется сигнал 
, при поступлении любой неправильной – сигнал 
.
Решение: Цифры 0 и 1 двоичных тетрад поступают на вход последовательно, пусть - соответствует поступлению на вход 0, - поступление 1, поэтому входной алфавит .
Событие R1 – содержит все слова, соответствующие неправильным тетрадам, а R2 – событие, содержащее слова, соответствующие правильным тетрадам.
Аналогично записывается РВ для R2 .
Пример 5. Построить автомат для выдачи магнитной карты в метро. Автомат принимает монеты достоинством 1 или 2 руб., карта стоит 4руб.
|
|
|
Решение: Входной алфавит X={1, 2} – в соответствии с монетами, которые может принимать автомат. Выходной алфавит – 1- выдача карты, 0 – отказ/ожидание, с – сброс/возврат денег, Y={1, 0, c}.
РВ, соответствующее выдаче карты – перебор комбинаций монет 1 и 2, чтобы получить требуемую сумму 4руб. в т.ч. без сдачи - 
РВ, описывающее сброс монет при неверной сумме – 
РВ при отказе – 
Граф автомата, построенный по приведенным РВ.
Отмеченная таблица переходов
| 0 | 0 | 0 | 0 | 1 | с | |
| S1 | S2 | S3 | S4 | S5 | S6 | |
| 1 | S2 | S3 | S4 | S5 | S2 | S2 |
| 2 | S3 | S4 | S5 | S6 | S3 | S3 |
| S1 | S2 | S3 | S4 | S5 | S6 | |
| 1 | S2 0 | S3 0 | S4 0 | S5 1 | S2 0 | S2 0 |
| 2 | S3 0 | S4 0 | S5 1 | S6 c | S3 0 | S3 0 |
| S1 | S2 | S3 | S4 | |
| 1 | S2 0 | S3 0 | S4 0 | S1 1 |
| 2 | S3 0 | S4 0 | S1 1 | S1 c |
Пример 6. Синтезировать автомат по продаже билетов стоимостью 5руб. Автомат может принимать монеты 1,2,5 руб.
Решение: Входной алфавит X={1, 2, 5} – в соответствии с монетами, которые может принимать автомат. Выходной алфавит – 1- выдача билета, 0 – отказ/ожидание, с – сброс/возврат денег, если введена неверная сумма (>5руб.), Y={1, 0, c}.
1) РВ, соответствующее выдаче билета – перебор комбинаций монет 1, 2, 5 чтобы получить требуемую сумму 5руб. без сдачи
2) РВ, соответствующее ожиданию – не вся сумма введена
3) РВ при Вводе неверной суммы – перебор возможных комбинаций.
Задание к работе:
Записать и проработать решения примеров 1-6.
Порядок выполнения работы:
1. Изучить инструкцию к практической работе.
2. Выполнить задание.
3. Оформить отчет.
Содержание отчета:
1. Тема.
2. Цель.
3. Задачи.
4. Материальное обеспечение.
5. Практическое задание.
Вопросы для самоконтроля:
1. Перечислите правила построения граф-схем переходов.
2. Объясните экспериментальный подход абстрактного автомата?
3. Дайте определение понятию дерево управления?
Практическая работа № 21
Тема: Структурный синтез автомата
Цель: овладение навыками анализа и синтеза структур конечных автоматов.
Материальное обеспечение: практическая работа, программное обеспечение
Дата добавления: 2019-02-22; просмотров: 1307; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!