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 шагов. 

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

S  wA

A  hB

B  iC

C  lD

D  eE

при обработке ключевого слова while вполне можно записать

S  while A.

Аналогичными могут быть правила

N₁  if N₂

M₀  integer M₁

и т.п.

Упражнения.

3.1. Постройте детерминированные А-грамматики для следующих цепочек, завершающихся символом “;”:

(a) целых чисел без знака и беззначащих нулей;

(б) четных целых чисел без знака;

(в) идентификаторов, содержащих четное количество символов;

(г) для цепочек из упражнения 1.5.

3.2. Постройте конечный автомат, который будет распознавать слова go to , причем между ними может быть произвольное число пробелов, включая нулевое.

3.3. Постройте конечные распознаватели для описанных ниже множеств цепочек из нулей и единиц:

(а) число единиц четное, а нулей - нечетное;

(б) между вхождениями единиц четное число нулей;

(в) за каждым вхождением пары 11 следует 0;

(г) каждый третий символ - единица;

(д) имеется по крайней мере одна единица.

3.4. Постройте конечный автомат с входным алфавитом {0,1}, который допускает в точности такое множество цепочек:

(а) все входные цепочки;

(б) все входные цепочки, кроме пустой;

(в) ни одной входной цепочки;

(г) входную цепочку 101;

(д) две входные цепочки: 01 и 0100;

(е) все входные цепочки, начинающиеся с 0 и заканчивающиеся на 1;

(ж) все цепочки, не содержащие ни одной единицы;

(з) все цепочки, содержащие в точности три единицы;

(и) все цепочки, в которых перед и после каждой единицы стоит 0;

3.5. Опишите словами множества цепочек, распознаваемых каждым из следующих автоматов:

3.6. Постройте детерминированную А-грамматику по следующей недетерминированной:

S  aAaBbBbD

A  aBaSbD

B  cScBbDb

D  dDdBbBbAac

3.7. Опишите словами множества цепочек, распознаваемых каждым из недетерминированных автоматов, изображенных на рисунке.

3.8. Найдите детерминированный автомат, эквивалентный следующему недетерминированному:

3.9. Найдите различающую цепочку (если она существует) для такой пары автоматов:

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

(а) каждое состояние имеет место хотя бы раз;

(б) каждый переход происходит хотя бы раз.

3.11. Постройте конечный автомат, который будет допускать только те цепочки, которые можно построить из подцепочек go, goto, too, on. Возможны повторения, но не пересечения. Так, одна из допустимых цепочек goongotoongotooon. Можно сначала построить недетерминированный автомат, а затем преобразовать его в детерминированный.

3.12. Найдите недостижимые состояния автомата

3.13. Найдите минимальные эквивалентные таблицы переходов для следующих автоматов:

40