Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 55
Текст из файла (страница 55)
Если последовательность конфигураций (вычисление) является допустимой (1еяа)) для МП-автомата Р (с точки зрения его определения), то вычисление, образованное путем дописывания одной и той же цепочки к концам входных цепочек всех его конфигураций, также допустимо. 2. Если вычисление допустимо лля МП-автомата Р, то вычисление, образованное дописыванием одних и тех же магазинных символов внизу магазина в каждой конфи- гурации, также допустимо. 3. Если вычисление допустимо для МП-автомата Р, и в результате некоторый суффикс ((ай) входной цепочки не прочитан, то вычисление, полученное путем удаления этого суффикса из входных цепочек каждой конфигурации, также допустимо.
Интуитивно данные, которые никогда не читаются МП-автоматом, не влияют на его вы- числения. Формализуем приведенные пункты! и 2 в виде следующей теоремы. ГЛАВА 6. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ 240 Теорема 6.5. Если Р = Я, Х, Г, 6, до, ~,, Р) — МП-автомат и (я, х, а) )- (р, у, 13), то лля любой цепоч ки и из Х* и у из Г верно следуюшее утверждение. (г), хи~, ау) )- (р, уи, ру) Заметим, что если у= я, то получается формальное утверждение приведенного выше принципа!, а при и = е — принципа2. Доказательство.
Доказательство проводится очень просто индукцией по числу шагов в последовательности МО, приводящих (д, хи, ау) к (р, уи, )Зу). Каждый из переходов в последовательности (гь х, а) 1- 1р, у, )3) обосновывается переходами Р без какого-либо Р использования и и/или у.
Следовательно, каждый переход обоснован и в случае, когда зти цепочки присутствуют на входе и в магазине. П Заметим, что обращение этой теоремы неверно. Существуют действия, которые МП- явтомат мог бы совершить с помощью выталкивания из стека, т.е. используя некоторые символы уи заменяя их в магазине, что невозможно без обработки у. Однако, как утверждает принцип 3, мы можем удалить неиспользуемый вход, так как МП-автомат не может прочитать входные символы, а затем восстановить их на входе. Сформулируем принцип 3 следующим образом. Нужны ли конфигурации конечных автоматовч Можно было бы удивиться, почему понятие конфигурации не было введено для конечных автоматов.
Хотя конечный автомат не имеет магазина, в качестве МО для него можно было бы использовать пару (д, и ), где г) — состояние, а и — остаток входа. Определить такие конфигурации можно, но их достижимость не дает никакой новой информации по сравнению с тем, что давало использование 6 . Иными словами, для любого конечного автомата можно показать, что 6 (о, и) = р тогда и только тогда, когда(д, згх) ~- 1р,х) для всех цепочек х.
Тот факт, что х может быть чем угодно, не влияюшим на поведение конечного автомата, является теоремой, аналогичной теоре- мам 6.5 и 6.6. Теорема 6.6. Если Р = (Д, Х, Г, 6, гу„, ~ж Р') — МП-автомат и 1д, хи, а) )- (р, уи, 13), то Р вернотакже, что(й,х, а) 1- (р,у, )3). П Р 6.1.5. Упражнения к разделу 6.1 6,1.1. Предположим, что МП-автомат Р = ((с), р), 10, 1), Щ,Х), 6, д, 4„(р)) имеет следующую функцию переходов. 1.
Ж), О, Хо) = ((~,.ТХ,)). 6.1. ОПРЕДЕЛЕНИЕ АВТОМАТОВ С МАГАЗИННОИ ПАМЯТЬЮ 241 2. б(р(, О,Х) = ((о, ХХ)). 3. б(р), 1, Х) = ((д, Х) ). 4. йд, е, Х) = ((Р, е) ). 5 р((Р, е, Х) = ((Р, яН б. б(р, 1, Х) = ((Р, ХХ)). 7. б(Р,1,2р) = ((Р, е)). Приведите все конфигурации, достижимые из начального МО (д, и, 2р), если входным словом ж является: а) 01; б) 0011; в) 010. б.2. Языки МП-автоллатов Мы предполагали, что МП-автомат допускает свой вход, прочитывая его и достигая заключительного состояния. Такой подход называется "допуск по заключительному состоянию". Существует другой способ определения языка МП-автомата, имеюший важные приложения. Для любого МП-автомата мы можем определить язык, "допускаемый по пустому магазину", т.е.
множество цепочек, приводящих МП-автомат в начальной конфигурации к опустошению магазина. Эти два метода эквивалентны в том смысле, что лля языка Е найдется МП-автомат, допускающий его по заключительному состоянию тогда и только тогда, когда для Е найдется МП-автомат, допускаюший его по пустому магазину. Однако для конкретных МП- автоматов языки, допускаемые по заключительному состоянию и по пустому магазину, обычно различны. В этом разделе показывается, как преобразовать МП-автомат, допускаюший Е по заключительному состоянию, в другой МП-автомат, который допускает Е по пустому магазину, и наоборот.
6.2.1. Допустимость по заключительному состоянию Пусть Р = (Д, Х, Г, б, р)р, 7„Р) — МП-автомат. Тогда Ь(Р), языком, допускаемым Р по заключительному состоянию, является (и ~ (Цр, и', Ур) (- (Р1, е, а)) для некоторого состояния р) из Р и произвольной магазинной цепочки а. Таким образом, начиная со стартовой конфигурации с и на входе, Р прочитывает и и достигает допускаюшего состояния. Содержимое магазина в этот момент не имеет значения.
ГЛАВА 6. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ Пример 6.7. Мы утверждали, что МП-автомат нз примера 6.2 допускает язык У,„ии состоящий нз цепочек вида и рр в алфавите (О, 1). Выясним, почему это утверждение верно. Ово имеет вид "тогда и только тогда, когда'*; МП-автомат Р нз примера 6,2 допускает цепочку х по заключительному состоянию тогда и только тогда, когда х имеет внд ви . (УУастаточнасть) Эта часть проста; нужно показать лишь допускающее вычисление В Если х = ичр~, то заметим, что справедливы следующие соотношения. (р(р, ичр", хр) )-(рур, и, и ср) (- (руь и, рр 2р) Р-(руь е, 2р) ~ — (дъ в, Ур) Таким образом, МП-автомат имеет возможность прочитать цепочку ж на входе и записать ее символы в свой магазин в обратном порядке.
Затем он спонтанно переходит в состояние ру~ и проверяет совпадение тр на входе с такой же цепочкой в магазине, н наконец, спонтанно переходит в состояние ру> (Необходимость) Эта часть труднее. Во-первых, заметим, что единственный путь достижения состояния рур состоит в том, чтобы находиться в состоянии ру, и иметь Лр на вершине магазина. Кроме того, любое допускающее вычисление Р начинается в состоянии рур, совершает один переход в ру, и никогда не возвращается в тур. Таким образом, дос- таточно найти условия, налагаемые на х, для которых (ар, х, 7р) (- (дп в, Лр); именно та- кяе цепочки и допускает Р по заключительному состоянию. Покажем индукцией по ф следующее несколько более общее утверждение. ° Если (рур, х, а),' (руь е, а), то х имеет вид ви .
Базис. Если х = г., то х имеет вид юи, с и = н Таким образом, заключение верно, н к ушерждение истинно. Отметим, что нам не обязательно доказывать истинность гипотезы (4ь Д а) ~- (РУь е, а), хотЯ она н веРна. Индукции. Пусть х = а,а,...а„для некоторого н > О. Существуют следующие два переходя, которые Р может совершить из МО (рур, х, а). !. (ру„х, а) у- (руьх, а). Теперь Р может только выталкивать из магазина, находясь в состоянии руь Р должен вытолкнуть символ из магазина с чтением каждого входного символа, и (х~>0.
Таким образом, если (руьх, а) у- (руь е, УЗ), то цепочка уЗ короче, чем а, и не может ей равняться. 2, (рур, а,аь..а„, рх) У- (рур, а,..а„, а,а). Теперь последовательность переходов может закончиться в ( уь е, а), только если последний переход является следующим выталкиванием. (руь а„, а,а) (- (руь в, а) В этом случае должно выполняться а, = а„.
Нам также известно, что (рур, а,...а„, а,а) у- (руь а„, а,а) 243 6.2. ЯЗЫКИ МП-АВТОМАТОВ По теореме 6.6 символ а„можио удалить из конца входа, поскольку ои ие использу- ется. Тогда (с),, а,...а„ь а,а) ( — (~уь к, оса) Поскольку вход у этой последовательности короче, чем и, можно применить иидуктивиое предположение и заключить, что аэ...а„, имеет вид)у для некоторого у. Поскольку х = асгу а„, и иам известно, что а~ — — а„, делаем вывод, что х имеет вид пи; в частиостии = а~у. к.
Приведенные рассуждения составляют сердцевину доказательства того, что х допускается только тогда, когда равен иэг~ для некоторого эг. Таким образом, необходимость доказана. Вместе с достаточностью, доказанной ранее, оиа гласит, что Р допускает в точности цепочки из с„„„„. П 6.2.2, Допустимость по пустому магазину Для каждого МП-автомата Р = (Д, Х, Г, б, суп У„Р) определим Н(Р) = ( ~ (г),1, Хе) ~- (Ч, ц а)), где д — произвольное состояние. Таким образом, Ж(Р) представляет собой множество входов к, которые Р может прочитать, одновременно опустошив свой магазии.~ Пример 6.8.
МП-автомат Р из примера 6.2 никогда ие опустошает свой магазин, поэтому У(Р) = И. Одиако небольшое изменение позволит автомату Р допускать А„„., как по пустому магазину, так и по заключительному состоянию. Вместо перехода ~до а Х,) = ((олХэ)) используем фасо а Х) = ((оп а)). Теперь Р выталкивает последний символ из магазина, когда допускает, поэтому ь(Р) = М,Р) = Л„,„„. П Поскольку множество допускающих состояний ие имеет значения, иногда в случаях, когда иас будет интересовать допуск только по пустому магазину, будем записывать МП-автомат в виде шестерки © Х, Г, 4 дь 20), опуская седьмой компонент.
6.2.3. От пустого магазина к заключительному состоянию Покажем, что классы языков, допускаемых МП-автоматами по заключительному состоянию и по пустому магазину, совпадают. В разделе 6.3 будет доказано, что МП- автоматы определяют КС-языки. Наша первая конструкция показывает, как, исходя из МП-автомата Рм допускающего язык ь' по пустому ма~азииу, построить МП-автомат Р„; допускающий ь по заключительному состоянию. Теорема 6.9. Если ь' ='г((РД для некоторого МП-автомата Рх = (Д, Х, Г, Бм Еь У,), то существует такой МП-автомат Рм у которого Х = ЦРк). ' Символ э' в М(Р) обозначает "пустой магазин' ("пой маей"), ГЛАВА б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
