Главная > Разное > Логика, автоматы, алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 3.7. Замечание об ограничении входных последовательностей

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

Если алфавит содержит символов, то может быть составлено различных последовательностей длины .

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

Примеры условий такого рода:

1. Допустимы лишь последовательности, в которых четные и нечетные индексы чередуются.

Например, последовательность . допустима, а последовательность . недопустима.

2. Допустимы лишь последовательности, в которых два одинаковых символа не следуют непосредственно друг за другом. Например, последовательность допустима, а последовательность недопустима.

3. Допустимы лишь последовательности, в которых после не следует непосредственно и т. д.

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

Совершенно аналогично обстоит дело и в любом ином случае, когда тактность связана с каким-либо заранее обусловленным «событием» на входе). При такой тактности допустимые входные последовательности всегда ограничены.

Таким образом, ограничения на возможные входные последовательности могут быть двух родов:

1. Они могут быть вынуждены особенностями тактности — в этом случае могут возникать лишь допустимые последовательности.

2. Они могут быть никак не связаны с тактностью, т. е., вообще говоря, П-машина могла бы реагировать на любые последовательности , но, по условиям применения, на входе П-машины появляются лишь допустимые последовательности.

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

<< Предыдущий параграф Следующий параграф >>
Оглавление