Пн. Июл 15th, 2024

Автоматы являются устройствами для переработки дискретной инфы. При всем этом нравом перерабатываемой инфы определяется входной и выходной алфавиты (X и Y); алфавит внутренних состояний (Q) определяется строением автомата и, вообщем говоря, он может различаться у различных автоматов с схожими входными и выходными алфавитами. Как следует, одно и то же преобразование инфы может быть осуществлено автоматами с различным числом состояний и, как следует, средством различного числа команд. Введем ряд определений:

Состояния q автомата М и q’ автомата М’ числятся эквивалентными, если оба автомата, получив одну и ту же (всякую) входную последовательность знаков, перерабатывают ее в схожую выходную последовательность.

Автоматы М и М’ именуются эквивалентными, если для каждого состояния автомата М существует эквивалентное ему состояние автомата М’ и напротив.

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

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

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

Автомат, эквивалентный данному и имеющий меньшее из всех вероятных число состояний именуется наименьшим.

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

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

От content

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Ads Blocker Image Powered by Code Help Pro

Обнаружен блокировщик рекламы! Пожалуйста, обратите внимание на эту информацию.

We\'ve detected that you are using AdBlock or some other adblocking software which is preventing the page from fully loading.

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

Пожалуйста, добавьте tehnar.info к вашему белому списку блокирования объявлений или отключите программное обеспечение, блокирующее рекламу.

Powered By
100% Free SEO Tools - Tool Kits PRO