Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений, страница 4

"Лексический анализатор" стандартного компилятора, т.е. тот компонент компилятора, который отвечает за разбивку исходного текста на такие логические единицьй как идентификаторы, ключевые слова и знаки пунктуации. 3. Программное обеспечение для сканирования таких больших текстовых массивов, как наборы Ч'еЬ-страниц, с целью поиска заданных слов, фраз или других последовательностей символов 1шаблонов). 4.

Программное обеспечение для проверки различного рода систем (протоколы связи или протоколы для зашишенного обмена информацией), которые могут находиться в конечном числе различных состояний. С точными определениями автоматов различного типа мы встретимся вскоре. А начнем с краткого описания того, что представляет собой конечный автомат, и как он действует. Существует множество различных систем и их компонентов, например, ГЛАВА 1. АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ 18 только что перечисленные, которые можно рассматривать, как находящиеся в каждый момент времени в одном из конечного числа "состояний".

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

Из состояния "выключено" нажатие кнопки переводит переключатель в состояние "включено'", и наоборот. На рис. 1.1 представлена конечноавтоматная модель переключателя. Как и для всех конечных автоматов, состояния обозначены кружками. В данном случае они отмечены как "вкл." и "выкл.". Дуги между состояниями отмечены "входными символами", задающими внешние воздействия на систему. В нашем случае это Нажатие, что означает нажатие на кнопку переключателя. Стрелки указывают, что всякий раз при Нажатии сис- тема переходит из одного состояния в другое. Нкчатиа Нач Начатиа Рис.

1.й Конечный автомат, моделирующий переключатель Одно нз состояний является так называемым "начальным состоянием*', Это состояние (в нашем случае — "выкл.*'), в котором система находится изначально. На рисунке оно отмечено словом Начало и стрелкой, указывающей на это состояние. Часто необходимо выделять одно или несколько "заключительных", или "допускающих", состояний.

Попав в одно из них в результате реализации некоторой последовательности входных воздействий,мы можем считать такую входную последовательность в определенном смысле "хорошей". Так, например, состояние "вкл." на рис.1.1 можно рассматривать как допускающее, поскольку если переключатель находится в этом состоянии, то устройство, управляемое им, находится в рабочем режиме. Допускающие состояния принято обозначать двойным кружком, хотя мы не использовали это обозначение на рис 1.1.

ьл 1.1. ЗАЧЕМ ИЗУЧАЕТСЯ ТЕОРИЯ АВТОМАТОВ1 19 Пример 1.2. Иногда состояние автомата запоминает гораздо более сложную информацию, чем выбор "вкл.— выкч.". На рис, 1.2 представлен конечный автомат, который может служить частью лексического анализатора. Его функцией является распознавание ключевого слова г1теп.

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

Состояние, обозначенное словом 'тпеп", достигается, когда по буквам введено все данное слово. Поскольку функция автомата заключается в распознавании слова сЬеп, то последнее состояние будем считать единственным допускающим. П 1.1.2. Структурные представления Следующие системы записи не являются автоматными, но играют важную роль в теории автоматов и ее приложениях.

1. Грамматики. Они являются полезными моделями при проектировании программного обеспечения, обрабатывающего данные рекурсивной структуры. Наиболее известный пример — "синтаксический анализатор". Этот компонент компилятора работает с такими рекурсивно вложенными конструкциями в типичных языках программирования, как выражения: арифметические, условные и т,п.

Например, грамматическое правило типа Е =» Е ч- Е означает, что выражение может быть получено соединением любых двух выражений с помощью знака "плюс". Это типичное правило построения выражений в существующих языках программирования. Ниже, в главе 5, будут определены так называемые контекстно-свободные грамматики. 2.

Регулярные выражения. Они также задают структуру данных, в частности, текстовых цепочек. Как будет показано в главе 3, шаблоны описываемых нми цепочек представляют собой то же самое, что задают конечные автоматы. Стиль этих выражений суще- ГЛАВА 1. АВТОМАТЫ: МЕТОДЫ И ПОНЯТИЯ 20 ственно отличается от стиля, используемого в грамматиках. Ограничимся простым примером. Регулярное выражение в стиле [])Ч!Х ' [А-г) [а-з] * [ ] [А-Е] [А-Е) ' представляет множество слов, начинающихся с прописной буквы, за которыми слелуют пробел и две прописные буквы. В тексте такое выражение задает шаблоны, которые могут быть названиями города и штата, например: 1с]заса [ЧУ [Итака, штат Нью-Йорк).

В этом выражении не учтено, что название города может состоять из нескольких слов, к примеру: Ра1о А1со сА [Пало-Альто, штат Калифорния). Чтобы учесть этот случай, приходится использовать более сложное выражение: ' ( [А-Е] [а-г]*[ ) ) *[ ] [А-Е) [А-Е1'. Для интерпретации подобных выражений достаточно знать лишь то, что [А-е] означает последовательность прописных букв английского алфавита от "А" до "Е" [т.е, любую прописную букву), а [ ] означает одиночный пробел. Кроме того, * значит "любое число вхождений" предшествующего выражения. Круглые скобки используются для группировки членов выражения и не являются символами описываемого текста.

1.1.3. Автоматы и сложносгь Автоматы являются существенным инструментом исследования пределов вычисли- мости. Как мы уже упоминали в начале главы, существуют следующие две важные проблемы. 1. Что компьютер вообще может? Это вопрос "разрешимости", а задачи, которые могут быть решены с помощью компьютера, называют "разрешимыми". Этой теме посвящена глава 9. 2. Что компьютер может делать эффективно? Это вопрос "труднорешаемости" задач. Те задачи, на решение которых компьютеру требуется время, зависящее от размера входных данных как некоторая медленно растущая функция, называют "легко разрешимыми".

"Медленно растущими" функциями чаще всего считаются полиномиальные, а функции, которые растут быстрее, чем любой полипом, считают расту- шими слишком быстро. Этот круг вопросов изучается в главе 1О. 1.2. Введение в теорию формальных доказательств Если вам довелось изучать планиметрию в школе до начала 1990-х, то, вероятнее всего, вам приходилось проводить подробные "дедуктивные доказательства" шаг за шагом, последовательно и детально обосновывая истинность некоторого утверждения.

Поскольку геометрия имеет свою практическую сторону (например, если вы хотите приобрести нужное количество коврового покрытия для комнаты, то вам нужно знать правило вычисления плошади прямоугольника), постольку и изучение общих методик формального доказательства в школе считалось весьма важным. 1.2. ВВЕДЕНИЕ В ТЕОРИЮ ФОРМАЛЬНЫХ ДОКАЗАТЕЛЬСТВ 21 В 1990-х годах в США стало модным учить доказательствам, основанным на субъективных ощущениях относительно истинности утверждения.