3.3. Линейное сжатие и ускорение автоматов

Автомат называется линейно-огранниченным по памяти, если для обработки цепочки длины n он использует не более pn ячеек памяти.

Автомат называется линейно-ограниченным по времени, если для обработки цепочки длины n он требует не более cn шагов по времени.

Здесь p,c  1 - некоторые малые константы.

Справедлива следующая теорема о линейном сжатии.

Теорема 3.1. Если язык распознается (обрабатывается) автоматом с оценкой pn по памяти, то можно построить автомат, распознающий тот же язык с оценкой pn/k, где k - целое число (n  k  1).

Доказательство. (Проведем его конструктивно, построением “сжатого” автомата для общего случая, когда автомат является преобразователем, то есть не только читает, но и пишет символы на ленту).

Пусть - внешний алфавит, - внутренний алфавит (множество состояний) исходного автомата, а k - заданная константа.

Построим новый внешний алфавит

,

состоящий из упорядоченных последовательностей по k символов старого алфавита и новое множество состояний , где

Смысл здесь состоит в том, что k старых символов из A предполагается записывать в одну клетку входной ленты.

Построим правила переходов. Пусть эти правила в исходном автомате имели вид:

,

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

Правила перехода нового автомата будут иметь вид:

(а) если то

где

если в исходном автомате был сдвиг входной головки;

если в исходном автомате был сдвиг ;

если в исходном автомате был сдвиг ;

(б) если и в исходном автомате был сдвиг , то

(в) если и в исходном автомате был сдвиг , то



С практической точки зрения такое сжатие не дает других преимуществ, кроме сокращения записи на ленте, тогда как число состояний линейно возрастает в k раз, число входных символов растет экспоненциально и время обработки цепочки не изменяется. Тем не менее, рассмотренная теорема дает основание сформулировать теорему о линейном ускорении, которую мы изложим, применительно к рассматриваемым конечным автоматам.

Теорема 3.2. Для любого конечного автомата можно построить эквивалентный ему автомат, распознающий цепочки длины n за n/k шагов, где k - целое число (n  k  1).

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

заменим на правила . 

Пример 3.5. Пусть автомат распознает цепочки вида dobyto, doto, doby и никаких других. Каждая правильная цепочка завершается символом #. Таким образом внешний алфавит предложенного автомата A = {d,o,b,t,#}. и его можно определить, используя восемь состояний с таблицей переходов, представленной на рис 3.11 (а).

Ускорим этот автомат в два раза, а для этого сначала сожмем его вдвое и получим новый входной алфавит, содержащий пары символов

= {<do>, <by>, <to>, <# >, <dy>, <db>, ...}.

Хотя таких пар будет всего 25, перечислять их все не имеет смысла. Правильные сочетания - это четыре первых пары приведенного множества. Встреча со всеми остальными всегда приводит к ошибке.

Новый автомат строим, заменяя пары правил перехода исходного автомата на одно правило результирующего. Например, правила dq₀  q₁

oq₁  q₂

заменяем на <do> Q₀  Q₂ ,

а правила bq₂  q₃

yq₃  q₄

на <by> Q₂  Q₄ .

В результате получим функциональную таблицу, приведенную на рис. 3.11 (б). Полученный автомат, обрабатывает входные цепочки за n/2 шагов. 