Алгоритм синтеза автомата Мура


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

оформить заявку

Слишком сложно? Тогда запросите консультацию специалиста!

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

ознакомиться с условиями

Краткое пояснение: Алгоритм синтеза автомата Мура

Методы абстрактного синтеза

Задача абстрактного синтеза заключается в составлении таблиц переходов и выходов автоматов по заданным условиям его функционирования, представленным в форме регулярных выражений. Абстрактный синтез обычно выполняется в два этапа:

1. Первый этап заключается в получении таблиц переходов и выходов в некоторой исходной форме. Построенный по этим таблицам автомат обычно содержит «лишние» внутренние состояния.

2. На втором этапе производится минимизация количества внутренних состояний заданного автомата.

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

Рассмотрим пример абстрактного синтеза автомата для случая, когда регулярные отношения составлены без применения операции итерации. Составим отмеченную таблицу переходов автомата, имеющего входной алфавит X{x1, x2} и реализующий следующий алгоритм.

S1 = x1x2 v x1x1x1
S2 = x1x2x2 v x2x2
Sзапр. =x1 vx2x2x2

При синтезе условимся начальное состояние автомата обозначать цифрой 0, а остальные состояния – десятичными числами 1, 2, 3 и т.д. Очевидно, самый простой, хотя и не экономный по числу используемых внутренних состояний автомата. Алгоритм синтеза заключается в следующем. Фиксируется начальное состояние и для входного слова, содержащего r букв, назначается r внутренних состояний. Переходы в автомате определяются так, что первая буква входного слова переводит автомат из начального состояния 0 в состояние 1, вторая буква из 1 в 2 и т.д. Аналогичные последовательности внутренних состояний назначаются для всех остальных слов. Затем все конечные состояния, в которые автомат попадает после подачи слов, входящих в событие Si, отмечаются выходными сигналами yi.

Чтобы система переходов автомата была определенной, для всех слов, имеющих одинаковые начальные отрезки, следует назначать одну и ту же последовательность состояний. Например, для регулярного события S1 первая буква x1 переводит автомат из начального состояния 0 в состояние 1, вторая буква x2 – из 1 в 2.

S1 = | x1 | x2 | v | x1 | x1 | x1 |
             
S2 = | x1 | x2 | x2 | v | x2 | x2 |
             

Поскольку первая буква второго слова x1x1x1, входящего в S1 также есть x1, то она переводит автомат из начального состояния 0 в 1. Вторая буква x1 переводит автомат из 1 в 3, третья – из 3 в 4.




Первые две буквы слова x1x2x2, входящего в S2, совпадают с первым словом события S1. Поэтому первые две буквы этого слова должны последовательно переводить автомат из 0 в 1, и из 1 в 2. Дальнейшие состояния обозначим числами 5, 6 и 7. Получившаяся в результате форма записи определяет разметку мест регулярных выражений.

Местами регулярного выражения называют промежутки между двумя буквами, между буквой и знаком дизъюнкции, а так же между буквой и скобкой. Кроме того, вводят начальное место, обозначаемое цифрой 0 и конечные места, отождествляемые с концом каждого слова. Для запрещенного события Sзапр последовательность событий можно не назначать. Для размеченных регулярных выражений составляется отмеченная таблица переходов.

  е е y1 e y1 y2 e y2 e
xjai *
x1 * * * * * *
x2 * * * * *

Чтобы система переходов автомата была определена при подаче любого входного слова, кроме состояний 0 - 7, вводится еще одно состояние, которое обозначается звездочкой *. В это состояние автомат переходит при подаче входных слов, которые не входят в события S1 и S2. Выходным сигналом y1 отмечены состояния 2 и 4, y2 – состояния 5 и 7. Остальные состояния отмечены пустой буквой e.

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



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


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

Хм, так же просматривали

Заказ

ФОРМА ЗАКАЗА

Бесплатная консультация

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

Этапность

СОПРОВОЖДЕНИЕ КЛИЕНТА

Получить работу можно всего за 4 шага

01
Оставляете запрос

Оформляете заказ работы, заполняя форму на сайте.

02
Узнаете стоимость

Менеджер оценивает сложность. Узнаете точную цену.

03
Работа пишется

Оплачиваете и автор приступает к выполнению задания.

04
Забираете заказ

Получаете работу в электронном виде на вашу почту.

Услуги

НАШ СЕРВИС

Что мы еще делаем?

icon
Дипломные работы

от 9800 рублей

ПОДРОБНЕЕ
icon
РГР (расчетно-графические работы)

от 230 рублей

ПОДРОБНЕЕ
icon
Проектные работы

от 3300 рублей

ПОДРОБНЕЕ
icon
Online помощь

от 380 рублей

ПОДРОБНЕЕ
icon
Решение задач

от 180 рублей

ПОДРОБНЕЕ
icon
Студенческие работы

от 80 рублей

ПОДРОБНЕЕ