Двухголовочные автоматы
Несмотря на то, что двухленточные и двухголовочные автоматы похожи друг на друга, их свойства сильно отличаются. Так, проблема пустоты разрешима для многоленточных автоматов и неразрешима для многоголовочных.
Более того, в последнем случае она не является даже частично разрешимой. Проблема эквивалентности также не является частично разрешимой для многоголовочных автоматов. Однако проблема эквивалентности разрешима для двухленточных автоматов, и остается пока открытой для многоленточных автоматов с тремя и более лентами.
Двухголовочный конечный автомат (ДКА) имеет одну ленту и две головки, которые могут независимо перемещаться вдоль ленты в одном направлении. Множество состояний Q разбито на два непересекающихся множества. В состояниях Q1 активна первая головка, а в состояниях Q2 - вторая.
Двухголовочный автомат можно рассматривать как такой двухленточный автомат, который работает с идентичными словами на обеих лентах.
Приведем пример ДКА, который проверяет равенство двух последовательно записанных слов в алфавите V = {0, 1}. Признаком окончания каждого из слов сделаем вспомогательный символ *, не входящий в V. Автомат должен допускать только слова вида а*, а 
V*. Пусть A = (V 
{*}, Q1 Q2, R, q01, #, I), где Q1 = { q01, q11, q21, q71 } - множество состояний, в которых активна первая головка; Q2 = { q32, q42, q52, q62 } - множество состояний, в которых активна вторая головка; R = { q71 } - множество, содержащее единственное заключительное состояние. Граф автомата показан на рис. 1.8, на котором вместо многих «параллельных» дуг с разными пометками нарисована одна дуга со всеми пометками.
|
|
|
Находясь в состоянии g01, автомат передвигает первую головку к началу второго слова и, обнаружив его, переходит в состояние q11. Если конец ленты # встречается раньше символа *, автомат переходит в незаключительное состояние q62. Если же автомат приходит к состоянию q11, он считывает поочередно символы второго слова первой головкой (состояние q11), а символы первого слова — второй головкой (состояния q32 и q52), сравнивая эти символы. Автомат возвращается каждый раз в состояние q11, если символы одинаковы. Если же обнаружится несовпадение символов или первая головка встречает конец слова раньше символа *, автомат уходит в состояние q62. Попав в это состояние, автомат не может выйти из него; перемещая вторую головку к концу слова на ленте, он достигает #, находясь в незаключительном состоянии, так что слово на ленте отвергается. Если первая головка достигнет конца второго слова, а вторая головка обнаружит, что первое слово тоже просмотрено до конца, то автомат перейдет в заключительное состояние q71. В противном случае автомат перейдет в состояние q62, отвергая слово.
|
|
|
Этот пример легко обобщить на случай произвольного алфавита V, увеличивая количество состояний множества Q.
Дата добавления: 2015-12-20; просмотров: 20; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!