Глава 3. Конечные автоматы

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

В результате изучения материала этой главы читатель должен усвоить:

• общее представление о конечноавтоматных преобразователях информации и их свойствах, методах их задания, особенностях двух основных типов конечноавтоматных преобразователях - автоматах Мили и Мура;

• проблемы минимизации и проверки эквивалентности конечных автоматов;

• методы реализации конечноавтоматных преобразователей;

• примеры применения КА в различных областях и методы графического формализма конечноавтоматного представления систем обработки информации;

• автоматные модели параллельных процессов и их использование для верификации.

Содержание главы 3:

Автоматное преобразование информации. Реализация КА. Эквивалентность КА: теорема Мура. Минимизация КА. Автоматы Мили и Мура. Примеры КА. Электронные часы. Схема управления микрокалькулятором. Визуальный формализм представления моделей систем с памятью: Statecharts. Графы переходов при представлении параллельных программ. Проблемы параллельных вычислений и верификация параллельных процессов на основе конечноавтоматной модели. Проблема умножения: алгоритм, который не может выполнить КА.

Примеры задач к главе 3:

1. Программа wc в UNIX считает во входном потоке слова, строки и символы. Поток завершается кодом eof. Слова разделены пробелами, символами табуляции ‘\t’ и символами перевода строки ‘\n’. Строки разделены символами перевода строки ‘\n’. Построить конечный автомат и на его основе программу wc.

2. Построить конечный автомат, выбрасывающий лишние пробелы в тексте.

Глава 4. Автоматные языки

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

В результате изучения материала этой главы читатель должен получить знания о:

• общих представлениях о языках, их распознавании и трансляции;

• методах распознавания автоматных языков;

• проблемах минимизации и проверки эквивалентности конечноавтоматных распознавателей;

• методах реализации распознавателей и трансляторов автоматных языков;

• примерах построения трансляторов автоматных языков;

• регулярных множествах и регулярные выражениях, их связь с автоматными языками;

• теоретических проблемах определения того, когда заданный язык является автоматным.

Содержание главы 4:

Языки. Грамматики. Автоматные грамматики и языки. Эквивалентность и минимизация конечноавтоматных распознавателей. Недетерминированные конечноавтоматные распознаватели. Синтаксические диаграммы. Связь синтаксических диаграмм и автоматных языков. Трансляторы автоматных языков. Транслятор языка ЛИНУР. Регулярные множества и регулярные выражения. Теорема Клини. Применение регулярных выражений: построение лексических анализаторов алгоритмических языков.

Примеры задач к главе 4:

1. Построить транслятор языка присваиваний с арифметическими выражениями без скобок и форматной печатью.

2. Построить детерминированный автомат, распознающий все цепочки, которые не содержат ни одной подцепочки языка, задаваемого регулярным выражением a*b.