Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 50
Текст из файла (страница 50)
Пусть г=(»Х, р). Определим ~4 как г,: ((о», р,), г) (г„(о», з), е,(р;, в))„ и множество р» ((»Х» Р») д ~ рп Р»н р2)' Тогда М»=(ч», Е, 14, г, Р») (см. пример 2.5). Построение Мв следует из ЛХ4 и Л14, так как А (ЛХа)»А (ЛХ») = А (ЛХ») й (У» ~А (ЛХ») ) = А (ЛХз) П А (Мв).
Построение Мв проводится подобно М4. Имеем Чв = = »',»4, ~в 14, однако Рв - ((йе Р»): д» ы Г» илп Р» ы Гз). Тогда ЛХв =(041 Т1 46» г1 рв)' При построении Мт лспольауется идея присоединения выхода из М» к входу Л1ь Однако при атом следует быть внимательными, чтобы не проделать лишний шаг прп движении от М» к ЛХь Итак, возьмем»',»т 0»~ Дз (разьединяющее объедппенпе ( ) изменяет названия так, что »,»» и Дт не имеют общих состояний, и использует »',1» 0 О»',»т), МИОХ»ЕСтВО Рв» РФР»~ Р,() Р„реп Г„ и добавим переходы от злементов Г» к другим состояниям ЛХм а именно Хт= 2» 0 840 ((Ь, з), Р»), гДе ЬыР»» Р»ы2з(Р з)>. Тогда М»=(Рп Е, Хп 9, Рт)' Построение Мв проводится аналогично.
Сначала необходимо позаботиться о том, чтобы Ав(ЛХ»)=8 было 329 представимо. Для этого добавим новое начальное состоя- ние и (и Ф ф) таким образом, чтобы выполнялись усло- вия чв = 0~ 0 (и), Г« = Р~ 0 (и), а г«расширим (так же, как н гг) следующим образом: г,ц(((и, г), о;), д;сна,(д, з), ген Х), г, () (((рп ), ч), 1«(чц з) ен Р„з ен Ч* Тогда Пример 2.5. На рис. 9.13 — 9.15 даются последовательность диаграмм состояний для машин М~ и Мз н результирующие составные машины Мз, ..., Мз, которые быля построены выше. Заметим, что некоторые ив этих машин являются недетерминированными, однако от недетерминированпости можно избавиться при помощи предыдущих результатов. г Построения, включающие объединение, конкатенацию и замыканве (операцня «звездочка«), обеспечивают основу алгебраических систем для описания множеств, представимых конечными распознавателями.
Эта алгебра будет обсуждаться в з 3, а в оставшейся части этого параграфа обратим внимание на моделирование реальных компьютеров. 2.гь Моделирование «реальных» компьютеров. Как уже отмечалось, если данный компьютер имеет память, состоящую из и битов, то для того, чтобы смоделировать его поведение, вообще говоря, необходим конечный автомат с 2' состояниями. Пусть начальное состояние имеет такую конфигурацию, что программа и значения данных находятси в «ядре». Тогда не существует внешних стимулов, которые могли бы дать начало последовательности переходов.
Однако рассмотрение машины в несколько другом виде может привести к выполнению команд, использующих конечное число (уже определенных) состояний машины. Предположкм, что память состоит иэ гл 1-битных слов; тогда и = т» й Теперь отделим программный указатель (называемый также программным счетчиком нли указателем следующеи команды) от оставшейся части машины; получим машину с л'=1»(л« вЂ” 1) битами памяти. (Для простоты предполагается, что указатель имеет ту же длину, что и другие компоненты памяти.) Теперь зэк можно программный указатель рассматривать после каждого изменения состояния н его значение использовать рыс. 9,14 для того, чтобы осуществлять очередной переход.
Таким образом, функция перехода имеет вкд $: ч~ХР- ДХР, где ~: (д, ра)- (д., рз) соответствует значению указателя рз, что означае': выделить команду из состояния о„ так, чтобы ыеревестн машыыу в состояние оо а зыачеыые 332 р, в программном указателе заменить на рз. (Здесь удобно рассматривать команду как действие, частично осуществляемое программным обеспечением, а частнчно— аппаратным методом, В этой модели мы не делаем различия между ними; на практике бывает, что программное обеспеченно — зто просто начальные данные, которые управляют аппаратными процессами.) Рвс.
эд5 Обычно программы начинают работу с программного указателя, установленного на определенное значение. Начиная с этого вначения, все последующие значения порождаются автоматически при помощи описанного выше процесса до тех пор, пока не выполнится команда останова. Конечно, не все 2' аначений, которые могут содержаться в программном указателе, должны быть верными. Часто 2' может быть болыпе вг, и, следовательно, 2' — вг аначеннй будут неправильнымн адресами в будут вызывать ошибку, приводящую к останову.
Число правильных аначений, которые может принимать программный укааатель, определяет число переходов, которые могут быть нарксованы в виде стрелок на каждого состояния. Однако это не ограничивает число состояний, которое равно 2" . При отсутствии дополнительной информации о моделируемой системе мы можем сказать о ней довольно мало, однако на один момент следует обратить внимание.
Если построенный нами конечный автомат останавливается за «короткое» время или под воздействием команды останова, илн из-аа полученного неправильного вначения указателя, то ревультат известен. Однако если машина ЗЗЗ продолжает считать в течение длительного проне кутка времени, то встает вопрос: остановится ли она когда-нибудь и получим лн мы результат) Поскольку машина конечна (и, следовательно, имеет ограниченную память), то зта задача разрешима, однако неизвестно, как долго ждать результат. В силу способа иостроенпя машины вара (д, р), являющаяся указателем состояния, единственным образом определяет последовательность состояний, которые должны последовать за данным состоянием, н, следовательно, повторение любой данной пары подразумевает бесконечный цикл.
Позтому, чтобы гарантировать, что последовательность вычислений никогда пе остановится, мы должны обеспечить, чтобы опа пересекала заданную дугу перехода дважды. Все зто требует достаточно много времеви, так как необходимо выполнить 2" в и = 2ьм М» т комапд. Даже при достаточно малых значениях т и ( число операций очень велико, и поэтому реальное время их выполнения требует десятков, сотен и даже тысяч лет. Урок, который мы должны извлечь из рассмотрения етого упражнения, заключается в том, что практически невозможно проверить корректпость программы разумных размеров, используя тестовые данные.
Требуется слишком много времени для выполнения всех прогонов программы. Такие тестовые прогоны могут только находить ошибки. У н р а ж н е н и е 9.2. (. Построить конечный автомат, который будет распознавать четные числа, записанные в двоичной форме и читаемые слева направо. 2. Построить конечный автомат с входным алфавитом (а, Ь), который останавливается в ааключительпом состоянии тогда и только тогда, когда входные данные пе содержат рядом двух соседних элементов а и двух соседних элементов Ь. 3.
Показать невозможность построения конечного автомата, на вход которого поступают только строки над алфавитом (а, Ь), и только те из иих являются представимыми, которые имеют равное количество символов пиЬ. 4. Построить (детерминированный) конечный автомат, для которого представимыми являются только строки над (О, (), состоящие из чередующихся единиц и нулей, следующих за чередующвмися парами из единиц и нулей. Ю4 5.
Придумать конечный автомат, способный распознавать десятичные числа, записанные в виде ~И~. А В~ и, где Ы ш (О, 1, 2, ..., 9). 5 3. Регулярная алгебра Способы комбинирования конечных распознавателей могут использоваться дли проверки аксиом множеств, из которых могут развиваться алгебраические системы. Классическая система, известная как регулярная алгебра, основана на трех операциях — объединении, пересечении и конкатенации, определенных на множестве строк. Уравнения в алгебре могут точно определять некоторые множества строк; зти множества являются решением уравнений (п.
3.1). Результаты, вытекающие из решений, имеют непосредственное применение к аспектам теории языков (п. 3.2). 3.1. Выражения и уравнения. Перед тем как дать формальное определение, мы введем две константы внутри системы. Существует множество строк 8 и (Л), которые обозначим символами О и 1 соответстиевво. Мы обосновываем их исяользов ание изображением конечных распознавателей соответственно на рис. 9.16, а и Ь. ф и Рзс. 9.16 Определение. Пусть Х вЂ” множество строк, представимое конечным распознавателем.
Говда Х называется регулярным выражением. Если Х и У обозначают множества строк, представимых двумя определенными маши- вами, то (в силу определения построения конечных распознавателей) Х 0 У (далее будем писать Х+ У), Х» и ХУ также являются регулярными выражениями. Разрешенные конструкции составных конечных автоматов предполагают следующие аксиомы для работы с произвольными регулярными выражениями А, В и С: 1) А+В В+А; 2) А+(В+С)-(А+В)+С; 3) А+А А; 4) А+О=А; 5) А(ВС)=(АВ)С; 6) А1 А =1А; 7) АО О=ОА; 8) А(В+С) АВ+АС; 9) (А+В)С АВ+ВС; 10) 0* 1; 11) А» А+Аз; 12) (А")э=Аз. Такую алгебраическую систему называют регрллр>сой алгеброй.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
