ГЛАВА 7. При изучении конечных автоматов мы обращали внимание на свойства самих автоматов и не касались свойств источников входных последовательностей

АВТОМАТЫ С ОГРАНИЧЕНИЯМИ НА ВХОДЕ

Введение

При изучении конечных автоматов мы обращали внимание на свойства самих автоматов и не касались свойств источников входных последовательностей, возбуждающих эти автоматы. Мы логично предполагали, что рассматриваемые автоматы могут подвергаться воздействиям со стороны любых источников сигналов, лишь бы генерируемые входные символы принадлежали входному алфавиту автомата. В этой главе мы откажемся от этого предположения и рассмотрим более общий класс автоматов, в котором на источники могут быть наложены определенные ограничения. Особо мы будем исследовать класс автоматов, известных как автоматы с ограничениями на входе, в которых не каждый входной символ может быть подан на автомат, находящийся в определенном состоянии. Такое ограничение неизменно возникает, поскольку существует некоторая взаимосвязь между внутренней структурой автомата и источником входных символов. Для иллюстрации рассмотрим пример 2 из § 1.7, где английский текст, состоящий из 26 букв алфавита и промежутков, просматривается с целью подсчета числа слов, начинающихся с «мл» и оканчивающихся на «d». Когда автомат находится, например, в состоянии «появление u-n-d», входной символ «p» не может быть подан, так как не существует английских слов, содержащих последовательность букв «und p» (или вероятность появления такой последовательности чрезвычайно мала).

Поэтому для всех практических целей символ «p» (так же как и многие другие символы) может быть исключен из множества входных символов, когда автомат, который описывает систему, просматривающую текст, находится в состоянии «появление u-n-d».

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