§ 3.7. Замечание об ограничении входных последовательностей
До сих пор мы предполагали, что последойательности входных символов могут быть, произвольными, лишь бы каждый из этих символов содержался в алфавите 
.
Если алфавит 
содержит 
символов, то может быть составлено 
различных последовательностей длины 
.
Часто возникают задачи, когда требуется рассматривать лишь последовательности символов, удовлетворяющие каким-либо дополнительным условиям. Последовательности, удовлетворяющие этим дополнительным условиям, назовем 
Примеры условий такого рода:
1. Допустимы лишь последовательности, в которых четные и нечетные индексы 
чередуются.
Например, последовательность 
. допустима, а последовательность 
. недопустима.
2. Допустимы лишь последовательности, в которых два одинаковых символа 
не следуют непосредственно друг за другом. Например, последовательность 
допустима, а последовательность 
недопустима.
3. Допустимы лишь последовательности, в которых после 
не следует непосредственно 
и т. д.
Ограничение последовательностей часто предопределено особенностями разбиения оси непрерывного времени на такты. Так, например, в случае, когда такт наступает всякий раз, когда происходит смена символа 
, возможные последовательности 
ограничены условием: два одинаковых символа не следуют непосредственно друг за другом.
Совершенно аналогично обстоит дело и в любом ином случае, когда тактность связана с каким-либо заранее обусловленным «событием» на входе). При такой тактности допустимые входные последовательности всегда ограничены.
Таким образом, ограничения на возможные входные последовательности могут быть двух родов:
1. Они могут быть вынуждены особенностями тактности — в этом случае могут возникать лишь допустимые последовательности.
2. Они могут быть никак не связаны с тактностью, т. е., вообще говоря, П-машина могла бы реагировать на любые последовательности 
, но, по условиям применения, на входе П-машины появляются лишь допустимые последовательности.
Различие это несущественно для нас, но случаи, когда входные последовательности не произвольны, а удовлетворяют каким-либо дополнительным условиям, будет далее предметом отдельного рассмотрения. В таких случаях основная таблица еще не задает автомата. Подобно тому как она должна быть доопределена условиями наступления такта, в подобных случаях она должна быть доопределена описанием того, какие входные последовательности допустимы.
