Модификации и виды автоматов

Введённое понятие автомата является достаточно общим. В литературе по теории автоматов (зачастую под разными названиями) рассматриваются более частные случаи, получаемые наложением тех или иных ограничений на компоненты Q, X, Y; Y, F автомата.

Но рассматриваются в литературе и вещи, не подпадающие под общее определение автомата, но как-то похожие на автомат. Собирательное название для такого рода вещей — модификации автоматов.

Например, если в определении автомата под Y и F понимать не функции из Q ´ X в Q и из Q ´ X в Y, а соответственно отношение Y Í Q ´ X ´ Q и отношение F Í Q ´ X ´ Y, то мы получаем более общее определение — определение так называемого недетерминированного автомата.

Автомат, определение который мы ввели раньше, выглядит при этом частным случаем недетерминированного автомата; и, если мы хотим подчеркнуть это обстоятельство, мы говорим, что наше предыдущее понятие автомата — это определение детерминированного автомата, получаемого в том специальном случае, когда отношения Y Í Q ´ X ´ Q и F Í Q ´ X ´ Y вырождаются в отображения или, что то же, когда указанные отношения удовлетворяют условию детерминистичности (однозначности).

Мы не будем рассматривать недетерминированные автоматы.

Ещё одна модификация автомата — так называемый асинхронный автомат. У него в качестве F вместо отображения из Q ´ X в Y используется отображение из Q ´ X в Y *.

И ещё одна модификация состоит в том что, вместо Y и F используются случайные функции. Это так называемые вероятностные автоматы.

Существуют или изобретаются и многие другие модификации.

Ни одна из них не будет нами рассматриваться.

Мы ограничимся изучением разновидностей обычного детерминированного автомата.

Как уже сказано, различные частные виды автоматов получаются наложением тех или иных ограничений на компоненты Q, X, Y; Y, F автомата общего вида.

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

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

В общем, предмет изучения современной теории автоматов можно схематически изобразить так.

Современная теория автоматов

модификации автоматов (детерминированные) автоматы

н.а., а.а., в.а., … (к. б.) а.б.п., ав.а., а.б.в., а.з., а.М.

н.а.б.в., мн.а.б.в.

Левая ветвь — не наше дело. Правая — это наш план на весь курс (сколько успеем).

Итак начнём.

А.б.п. (автомат без памяти). Автомат без памяти — это тройка (X, Y; F), где F — отображение входного алфавита X в выходной алфавит Y, т.е. F: X ® Y.

Иначе говоря, команды автомата без памяти имеют вид x _r ® y_s, где x_r Î X, y_s Î Y.

Рекуррентные соотношения (1) принимают в этом случае вид

y (t) = F [ x (t)], (1а)

т.е. выходной символ на данном такте (для данного t) зависит только от входного символа на данном такте и нисколько не зависит от остальных символов.

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

Иными словами, каждый а.б.п. реализует единственный словарный (и единственный сверхсловарный) оператор, который осуществляет «побуквенный перевод» входных символов в выходные. Такие операторы называются истинностными операторами или операторами без памяти.

Число всех автоматов без памяти с данными конечными алфавитами X = { x ₁, x ₂, …, x _m}, Y = { y ₁, y ₂, …, y _n} равно n^m.

Ав.а. (автономный автомат). Автономный автомат — это четвёрка (Q, Y; Y, F), где Y и F отображают Q в Q и Q в Y соответственно.

Команды автономного автомата имеют вид q_i ® q_j y_s, а рекуррентные соотношения (1) —

q (t + 1) = Y [ q (t)],

y (t) = F [ q (t)]. (1б)

При каждой фиксации (2) начального состояния q (1) = q ₀ автономного автомата соотношения (1б) однознчно определяют единственное выходное сверхслово y (1) y (2) … и единственное внутреннее сверхслово q (1) q (2) …

Очевидно, если автономный автомат конечен и число его состояний равно k, то уже среди значений q (1) q (2) … q (k + 1) найдутся повторяющиеся состояния.

Следовательно, каждое из двух сверхслов y (1) y (2) … и q (1) q (2) … окажется периодическим (не обязательно чисто периодическим, т.е., быть может, с некоторым предпериодом) и с длиной периода, не превышающей числа состояний автомата.

Число автономных автоматов с данными алфавитами Q = { q ₁, …, q_k }и Y = { y ₁, y ₂, …, y _n}равно (nk) ^k.

А.б.в. (автомат без выхода). Автомат без выхода — это тройка (Q, X; Y)., где Y отображает Q ´ X в Q.

Команды автомата без выхода принимают вид q_i x _r ® q_j, а из рекуррентных соотношений (1) сохраняется лишь первое:

q (t + 1) = Y [ q (t), x (t)]. (1в)

Общее число автоматов без выхода с алфавитами Q = { q ₁, …, q_k } и X = { x ₁, x ₂, …, x _m} равно k ^mk.

Поведение автомата без выходов не может быть охарактеризовано в терминах словарных (или сверхсловарных) операторов, перерабатывающих входные слова (сверхслова) в выходные слова (сверхслова).

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

Однако для автоматов без выхода интереснее определить поведение не в терминах операторов, а в терминах языков и сверхъязыков.

Пусть для автомата M = (Q, X; Y) зафиксированы состояние q ₀, и входное слово x = x (1) x (2) x (3) … x (r). Тогда рекуррентные соотношения

q (1) = q ₀, q (t + 1) = Y [ q (t), x (t)]

однозначно определяют внутреннее слово q (1) q (2) … q (r) q (r + 1). Обратите внимание: слово x имеет длину r, а слово q — длину r + 1.

Если при этом q (r + 1) = q ¢, то будем говорить, что слово x переводит состояние q ₀ в состояние q ¢.

Настроенным автоматом (без выхода) называется тройка (M, q ₀, Q ¢), где M — автомат без выхода, q ₀ — некоторое выделенное его состояние (начальное состояние), Q ¢ — некоторое подмножество множества Q его состояний (Q ¢ — множество финальных состояний).

Множество (быть может пустое) всех входных слов, каждое из которых переводит q ₀ в какое-либо финальное состояние q Î Q ¢, называется языком, представляемым настроенным автоматом (M, q ₀, Q ¢), или его поведением, и обозначается через w (M, q ₀, Q ¢).

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

А именно, подача входного слова x = x (1) x (2) x (3) … x (r) на вход автомата истолковывается как вопрос: принадлежит ли это слово интересующему нас языку?

Если в результате подачи слова автомат окажется в финальном состоянии, то ответ утвердителен; в противном случае он отрицателен.

Теперь пойдём дальше.

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

Пусть дано некоторое сверхслово a = a (1) a (2) … в алфавите A.

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

Например, буква a — предельный символ для сверхслова bbaaaaa …, а буква b — не предельный символ для этого же сверхслова.

Обозначим через lim x множество всех символов, предельных для сверхслова x.

Зафиксируем в автомате M = (Q, X; Y) состояние q ₀ и входное сверхслово x = x (1) x (2) ….

Тогда рекуррентное соотношение (1в) плюс начальное условие q (1) = q ₀ однозначно определяют некоторое внутреннее сверхслово q = q (1) q (2) ….

Мы могли бы сказать, что автомат M с начальным состоянием q ₀ переводит входное сверхслово x во внутреннее сверхслово q.

Но вместо этого предпочитаем говорить, что входное сверхслово x переводит состояние q ₀ автомата M в предельное множество состояний Q ¢, где Q ¢ = lim q.

Очевидно, что Q ¢ Í Q.

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

Это приводит нас к следующим определениям.

Макросостоянием автомата назовём любое подмножество его состояний.

Макронастроенным автоматом называется тройка (M, q ₀, C), где M — автомат без выхода, q ₀ — выделенное (начальное) его состояние, C — произвольно выделенное множество его макросостояний (называемых предельными макросостояниями).

Пусть задан макронастроенный автомат (M, q ₀, C). Тогда множество всех сверхслов, каждое из которых переводит q ₀ в какое-либо предельное макросостояние Q ¢Î C, называется сверхъязыком, представляемым в макронстроенном автомате (M, q ₀, C), и обозначается W (M, q ₀, C).

КОНЕЦ.

Дата добавления: 2014-01-03