Бильгаева Н.Ц. - Теория алгоритмов, формальных языков, грамматик и автоматов, страница 13

Это состояние будет начальным для следующей серии испытаний.Эти задачи анализа получили название экспериментов по распознаванию состояния.5.7.1. Автомат МилиАвтомат Мили - это пятерка вида M = (К, X, Y, f, g), где:K - множество состояний автомата;X - входной алфавит;Y - выходной алфавит;f - функция переходов (отображение K ⋅ X → K);g - функция выходов (отображение K ⋅ X → Y).Как и любой другой автомат, автомат Мили можно представить в виде таблицыили графа. В графе переходов автомата Мили на дугах указываются через символ ‘/’входные и выходные символы.

Таблица переходов состоит из двух частей: в левой частизаписываются значения функции выходов, в правой части - значения функции переходов.Пример. Построим преобразователь,выражения, порождаемые грамматикой:которыйраспознаетарифметическиеS → a+S | a−S | +S | −S | aи устраняет из этих выражений избыточные унарные операции.

Например, выражение –a+−а−+−а он переведет в –а−а+а. Во входном языке символ а представляет идентификатори перед идентификатором допускается произвольная последовательность знаков унарныхоперации + и −. Заметим, что входной язык является регулярным множеством.Пусть M = (К, X, Y, f, g), где1. К = {q0, q1, q2, q3, q4},2. X = {a,+, −},3. Y = X.Преобразователь М начинает работу в состоянии q0 и, чередуя состояния q0 и q4 навходном символе «−», определяет, четное или нечетное число знаков − предшествуетпервому символу а. Когда появляется а, преобразователь М переходит в состояние q1,допуская вход, и выдает а или −а в зависимости от того, четно или нечетно числопоявившихся минусов.

Для следующих символов а он подсчитывает, четно или нечетночисло предшествующих минусов, с помощью состояний q2 и q3. Единственное различиемежду парами q2, q3 и q0, q4 состоит в том, что если символу а предшествует четное числоминусов, то первая из них выдает +а, а не только а.Таблица переходов выглядит следующим образом:К\Хq0q1q2q3q4aa+a−a−aY+εεεεε−εεεεεaq1q1q1q1K+q0q2q2q3q4−q4q3q3q2q05.7.2. Автомат МураАвтомат Мура - это «пятерка» вида U = (К1, X, Y, f1, h), где:K1 - множество состояний автомата;X - входной алфавит;Y - выходной алфавит;f1 - функция переходов (отображение K ⋅ X → K);h - функция выходов (отображение K ⋅ X → Y).При представлении автомата Мура графом дуги помечаются символами входногоалфавита, а каждая вершина графа - состоянием и символом выходного алфавита.При формальном сравнении определений автоматов Мили и Мура может показаться, чтоавтомат Мура может быть задан как входонезависимый автомат Мили, т.е.

такой автоматМили, выходная функция которого удовлетворяет следующим условиям: ∀ a ∈ X, ∀ b ∈ X, ∀z ∈ Z (g(z, a) = g(z, b)). Однако это не соответствует способу функционирования автоматовМура в соответствии с введенным определением.В автомате Мура реализована иная временная связь между переходами из одногосостояния в другое и выходом, по сравнению с автоматом Мили, у которого выход,соответствующий некоторому входу и определенному состоянию, порождается во времяперехода автомата в следующее состояние.

У автомата Мура сначала порождается выход, апотом - переход в следующее состояние, причем выход определяется только состояниемавтомата.5.7.3. Равносильность автоматов Мили и МураРавносильность заключается в том, что множество реакций этих автоматов совпадает:L(M) = {qz | qZ ∈ K};L(U) = {ht | ht ∈ K1};L(M) = L(U).Теорема. Для каждого автомата Мура можно построить равносильный автомат Мили.Доказательство.

Граф равносильного автомата Мили M можно получить в том случае,если каждому ребру автомата Мура U сопоставить ребро автомата M.Пусть w = x1 x2 ... xn - входная цепочка, тогда множества реакций для автоматов M и Uбудут соответственно представлены следующим образом:q0 / y1, x1 → q1 / y2, x2 → ... → qn-1 / yn, xn;q0, x1 / y1 → q1, x2 / y2 → ... → qn-1, xn / yn.Теорема. Для любого автомата Мили можно построить эквивалентный автомат Мура.Доказательство.

В качестве множества K1 автомата Мура возьмем K1 = K ⋅ Y. Дляобеспечения равносильности автоматов M = U функции переходов и выходов определимследующим образом:f1(p ⋅ y, a) = {qb | f(p, a) = q, b ∈ X};h(p ⋅ y) = y.Если реакция автомата M на входную цепочку вида w = x1 x2 ... xn из состояния q0 имеетвидq0, x1 / y1 → q1, x2 / y2 → ... → qk-1, xk / yk(1),то существует такое состояние q0⋅x1 недетерминированного автомата U, что, начинаяработу из этого состояния, автомат U выполняет следующие действия:q0 ⋅ x1 / y1 → q1 ⋅ x2 / y2 → ... → qk-1 ⋅ xk / yk, xk(2).Аналогично можно доказать и обратную теорему о том, что из существования реакции(2) следует существование реакции (1), что подтверждает равносильность автоматов Мили иМура.5.7.4.

Задания для самостоятельной работы.1. Построить конечный преобразователь, моделирующий работу светофора. Рассмотретьразличные алгоритмы переключения светофора.2. Построить автомат Мили, который читает текст, написанный на русском языке.Автомат должен считать все слова, начинающиеся с символа "б" и оканчивающиесясимволом "т", т.е. такие, как "бит", "байт", "батут" и т.д.

При построении автомата всебуквы кроме "б" и "т" можно обозначить каким-либо символом, например, "|".3. Построить автомат Мили, который читает программу, написанную на языкепрограммирования высокого уровня. Автомат должен считать все целые константы.ЗАКЛЮЧЕНИЕВсякий алгоритм можно рассматривать как некоторое универсальное средство длярешения целого класса задач. Но существуют такие классы задач, для решения которых нетобщего универсального алгоритма. Проблемы решения такого рода задач называютсяалгоритмически неразрешимыми проблемами. Однако алгоритмическая неразрешимостьпроблемы решения задач того или иного класса не означает невозможность решения любойчастной задачи из этого класса.

Переход от интуитивного понятия алгоритма к формальномуопределению алгоритма (рекурсивные функции, машины Тьюринга) позволяет доказатьалгоритмическую неразрешимость ряда проблем.Понятия, алгоритмы и методы теории формальных языков, грамматик и автоматовявляются теоретической основой современной теории программирования, построенияалгоритмических языков, проектирования языковых процессоров, в частности,компиляторов, ассемблеров, макрогенераторов и т.д.Рекомендуемая литература1. Алферова З.В. Теория алгоритмов. - М.: Статистика, 1973.2. Ахо А., Ульман Дж.

Теория синтаксического анализа, перевода, компиляции. В 2 т. Т.1, 2. - М.: Мир, 1980.3. Брауэр В. Введение в теорию конечных автоматов. -М.: Радио и связь, 1987.4. Гинзбург С. Математическая теория контекстно-свободных языков. - М.: Мир, 1970.5. Гросс М., Лантен А. Теория формальных грамматик.- М.: Мир, 1971.6. Крючкова Е.Н. Теория алгоритмов. - Барнаул; 1995.7. Крючкова Е.Н.

Теория формальных языков и автоматов. - Барнаул; 1996.8. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.:Энергоатомиздат, 1988.9. Любимский Э.3., Мартынюк В.В., Трифонов Н.П. Программирование. - М.: Наука,1980.10. Мелихов А.Н., Кодачигов В.И. Теория алгоритмов и формальных языков. - Таганрог;1983.11. Рейуорд - Смит В. Дж. Теория формальных языков. Вводный курс. - М.: Мир, 1988.12. Саломаа А. Жемчужины теории формальных языков. - М.: Мир, 1987.ОГЛАВЛЕНИЕВведение1.

Основные понятия теории алгоритмов1.1. Предварительные сведения1.2. Основные требования к алгоритмам1.3. Математическое определение алгоритма1.4. Понятие алфавитного оператора1.5. Задания для самостоятельной работы2. Рекурсивные функции2.1. Общие сведения2.2. Понятие простейших функций2.2.1. Оператор суперпозиции2.2.2.

Оператор примитивной рекурсии2.2.3. Оператор минимизации2.2.4. Ограниченный оператор минимизации2.3. Примитивно-рекурсивные и частично-рекурсивные функции2.4. Типы рекурсивных алгоритмов2.5. Методика решения задач2.5.1. Использование оператора примитивной рекурсии2.5.2. Использование оператора минимизации2.5.3. Использование ограниченного оператора минимизации2.6. Задания для самостоятельной работы3.

Машины Тьюринга3.1. Общие сведения3.2. Неформальное определение машины Тьюринга3.3. Формальное определение машины Тьюринга3.4. Способы представления машины Тьюринга3.4.1. Представление машины Тьюринга совокупностью команд3.4.2. Представление машины Тьюринга графом3.4.3. Представление машины Тьюринга таблицей соответствия3.5. Вычислимые функции3.6.

Операции над машинами Тьюринга3.7. Примеры построения машин Тьюринга3.8. Машина Тьюринга с полулентой3.9. Универсальная машина Тьюринга3.10. Алгоритмически неразрешимые проблемы3.11. Задания для самостоятельной работы4. Формальные грамматики и языки4.1. Общие сведения4.2. Основные понятия порождающих грамматик4.3. Классификация грамматик4.3.1. Методика решения задач4.4. Грамматический разбор4.4.1. Представление грамматики в виде графа4.5. Преобразования КС-грамматик.4.5.1. Удаление правил вида А → В4.5.1.1.

Графическая модификация метода4.5.2. Построение неукорачивающей грамматики4.5.3. Построение грамматики с продуктивными нетерминалами4.5.4. Построение грамматики, аксиома которой зависит от всех нетерминалов4.5.5. Удаление правил с терминальной правой частью4.5.6. Построение эквивалентной праворекурсивной КС-грамматики4.6.

Задания для самостоятельной работы5. Автоматы5.1. Понятие автомата. Типы автоматов5.2. Формальное определение автомата5.3. Распознаватели5.3.1. Языки и автоматы5.3.2 Регулярные множества5.3.3. Операции над регулярными языками5.3.4. Автоматные грамматики5.4. Автоматы с магазинной памятью(МП-автоматы)5.4.1. Восходящий разбор в МП-автомате5.4.2.

Нисходящий разбор в МП-автомате5.5. Выводы5.6. Понятие преобразователей5.7. Автоматы Мили, Мура5.7.1. Автомат Мили5.7.2. Автомат Мура5.7.3. Равносильность автоматов Мили и Мура5.7.4. Задания для самостоятельной работыЗаключениеРекомендуемая литератураОглавлениеТаблица 1входмагазинpaB0p0/aB0р0AB0p0SB0p0(/SB0p0a(/SB0p0+a(/SB0p0A(/SB0p0S(/SB0p0A+S(/SB0p0)a+S(/SB0p0A+S(/SB0p0S(/SB0p0)S(/SB0p0A/SB0p0SB0p0B0fТаблица 2входмагазинpaB0p0SB0p1S/AB0p1а/AB0p1a/AB0p1/(/AB0p1(S)B0p1AB0p1S)B0p1S+A)B0p1A+A)B0p1a+а+A)B0p1+A)B0p1A)B0p1a)a)B0p1)B0p1B0f.