dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Простейшим нетривиальным конечным автоматом является переключатель “включено-выключено”. Это устройство помнит свое текущее состояние, и от этогосостояния зависит результат нажатия кнопки. Из состояния “выключено” нажатие кнопки переводит переключатель в состояние “включено”, и наоборот.На рис. 1.1 представлена конечноавтоматная модель переключателя.

Как и для всехконечных автоматов, состояния обозначены кружками. В данном случае они отмеченыкак “вкл.” и “выкл.”. Дуги между состояниями отмечены “входными символами”, задающими внешние воздействия на систему. В нашем случае это Нажатие, что означает нажатие на кнопку переключателя. Стрелки указывают, что всякий раз при Нажатии система переходит из одного состояния в другое.НажатиеНачаловыкл.вкл.НажатиеРис. 1.1. Конечный автомат, моделирующий переключательОдно из состояний является так называемым “начальным состоянием”. Это состояние(в нашем случае — “выкл.”), в котором система находится изначально. На рисунке оноотмечено словом Начало и стрелкой, указывающей на это состояние.Часто необходимо выделять одно или несколько “заключительных”, или “допускающих”, состояний.

Попав в одно из них в результате реализации некоторой последовательности входных воздействий, мы можем считать такую входную последовательностьв определенном смысле “хорошей”. Так, например, состояние “вкл.” на рис. 1.1 можнорассматривать как допускающее, поскольку если переключатель находится в этом состоянии, то устройство, управляемое им, находится в рабочем режиме. Допускающие состояния принято обозначать двойным кружком, хотя мы не использовали это обозначение на рис 1.1. †1.1. ÇÀ×ÅÌ ÈÇÓ×ÀÅÒÑß ÒÅÎÐÈß ÀÂÒÎÌÀÒÎÂ?Стр. 1919Пример 1.2. Иногда состояние автомата запоминает гораздо более сложную информацию, чем выбор “вкл.–выкл.”.

На рис. 1.2 представлен конечный автомат, который может служить частью лексического анализатора. Его функцией является распознаваниеключевого слова then. Этот автомат должен иметь пять различных состояний, каждоеиз которых представляет позицию в слове then, достигнутую на данный момент. Этипозиции соответствуют префиксам слова, от пустой цепочки (никакая позиция в словееще не достигнута) до целого слова.НачалоthtethnthethenРис. 1.2. Конечный автомат, моделирующий распознавание слова thenНа рис.

1.2 каждое из пяти состояний обозначено частью слова, прочитанной на данномшаге. Входным сигналам соответствуют буквы. Мы можем считать, что данный лексический анализатор всякий раз просматривает по одному символу компилируемой программы.Каждый следующий символ рассматривается как входной сигнал для данного автомата.Начальное состояние автомата соответствует пустой цепочке, и каждое состояние имеетпереход по очередной букве слова then в состояние, соответствующее следующему префиксу.

Состояние, обозначенное словом “then”, достигается, когда по буквам введено вседанное слово. Поскольку функция автомата заключается в распознавании слова then, топоследнее состояние будем считать единственным допускающим. †1.1.2. Ñòðóêòóðíûå ïðåäñòàâëåíèÿСледующие системы записи не являются автоматными, но играют важную роль втеории автоматов и ее приложениях.1.Грамматики.

Они являются полезными моделями при проектировании программного обеспечения, обрабатывающего данные рекурсивной структуры. Наиболееизвестный пример — “синтаксический анализатор”. Этот компонент компилятораработает с такими рекурсивно вложенными конструкциями в типичных языкахпрограммирования, как выражения: арифметические, условные и т.п. Например,грамматическое правило типа E ⇒ E + E означает, что выражение может бытьполучено соединением любых двух выражений с помощью знака “плюс”. Этотипичное правило построения выражений в существующих языках программирования.

Ниже, в главе 5, будут определены так называемые контекстно-свободные грамматики.2.Регулярные выражения. Они также задают структуру данных, в частности, текстовыхцепочек. Как будет показано в главе 3, шаблоны описываемых ими цепочек представляют собой то же самое, что задают конечные автоматы. Стиль этих выражений суще-20Стр. 20ÃËÀÂÀ 1. ÀÂÒÎÌÀÒÛ: ÌÅÒÎÄÛ È ÏÎÍßÒÈßственно отличается от стиля, используемого в грамматиках. Ограничимся простымпримером.

Регулярное выражение в стиле UNIX ’[A-z][a-z]*[ ][A-Z][A-Z]’представляет множество слов, начинающихся с прописной буквы, за которымиследуют пробел и две прописные буквы. В тексте такое выражение задает шаблоны, которые могут быть названиями города и штата, например: Ithaca NY(Итака, штат Нью-Йорк). В этом выражении не учтено, что название города можетсостоять из нескольких слов, к примеру: Palo Alto CA (Пало-Альто, штат Калифорния). Чтобы учесть этот случай, приходится использовать более сложноевыражение: ’([A-Z][a-z]*[ ])*[ ][A-Z][A-Z]’. Для интерпретации подобных выражений достаточно знать лишь то, что [A-Z] означает последовательность прописных букв английского алфавита от “A” до “Z” (т.е.

любую прописнуюбукву), а [ ] означает одиночный пробел. Кроме того, * значит “любое число вхождений” предшествующего выражения. Круглые скобки используются для группировки членов выражения и не являются символами описываемого текста.1.1.3. Àâòîìàòû è ñëîæíîñòüАвтоматы являются существенным инструментом исследования пределов вычислимости. Как мы уже упоминали в начале главы, существуют следующие две важныепроблемы.1.Что компьютер вообще может? Это вопрос “разрешимости”, а задачи, которые могут быть решены с помощью компьютера, называют “разрешимыми”. Этой темепосвящена глава 9.2.Что компьютер может делать эффективно? Это вопрос “труднорешаемости” задач.Те задачи, на решение которых компьютеру требуется время, зависящее от размеравходных данных как некоторая медленно растущая функция, называют “легко разрешимыми”.

“Медленно растущими” функциями чаще всего считаются полиномиальные, а функции, которые растут быстрее, чем любой полином, считают растущими слишком быстро. Этот круг вопросов изучается в главе 10.1.2. Ââåäåíèå â òåîðèþ ôîðìàëüíûõ äîêàçàòåëüñòâЕсли вам довелось изучать планиметрию в школе до начала 1990-х, то, вероятнее всего, вам приходилось проводить подробные “дедуктивные доказательства” шаг за шагом,последовательно и детально обосновывая истинность некоторого утверждения.

Поскольку геометрия имеет свою практическую сторону (например, если вы хотите приобрестинужное количество коврового покрытия для комнаты, то вам нужно знать правило вычисления площади прямоугольника), постольку и изучение общих методик формальногодоказательства в школе считалось весьма важным.1.2. ÂÂÅÄÅÍÈÅ Â ÒÅÎÐÈÞ ÔÎÐÌÀËÜÍÛÕ ÄÎÊÀÇÀÒÅËÜÑÒÂСтр. 2121В 1990-х годах в США стало модным учить доказательствам, основанным на субъективных ощущениях относительно истинности утверждения.

Конечно, неплохо уметь чувствовать истинность необходимого вам утверждения, однако плохо то, что в школе теперь не изучают весьма важные методики доказательств. А между тем, всякий, кто занимается информатикой, должен уметь понимать доказательства. Некоторые специалистыв области информатики придерживаются крайней точки зрения, полагая, что формальноедоказательство корректности программы должно идти рука об руку с ее написанием.Продуктивность такого подхода вызывает сомнение. С другой стороны, есть и такие, которые считают, что в программировании как дисциплине нет места доказательствам.Среди них популярен девиз: “Если ты не уверен в правильности своей программы —запусти ее и убедись”.Мы занимаем промежуточную позицию по отношению к этим полярным подходам.Тестирование программ, безусловно, важно.

Однако тестирование проходит до поры довремени, поскольку вы не в состоянии проверить работу вашей программы для всех возможных входных данных. Важнее, что, если ваша программа достаточно сложна(скажем, какая-нибудь хитрая рекурсия или итерация), то, не зная точно, что происходитпри входе в цикл или рекурсивном вызове некоторой функции, вы вряд ли сумеете вернозаписать код. Получив сообщение об ошибке, вам все равно придется искать правильноерешение.Чтобы правильно выполнить рекурсию или итерацию, необходимо предварительнопостроить некую индуктивную гипотезу, причем полезно обосновать формально илинеформально, что эта гипотеза остается истинной при рекурсии или итерации. В сущности, процедура уяснения механизма работы правильно написанной программы —это то же самое, что процедура доказательства по индукции теоремы.

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

Характеристики

Список файлов книги