ЛЕКЦИЯ 3. РАСПОЗНАВАНИЕ ЯЗЫКОВ МАШИНАМИ ТЬЮРИНГА

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

a+b

c-d*e

-f

и пр.

Некорректными выражениями, очевидно, являютcя a++b c- или c--- и др. Построим простую машину, которая получая на вход такие выражения, за конечное время определит, является ли выражение корректным или нет. В первом случае машина закончит свою работу в состоянии YES, а во втором – в состоянии NO. Подобные машины называют распознающими. Распознать некоторый объект – значит определить, удовлетворяет ли он определенным условиям или нет. Задача распознавания в общем может быть неразрешимой. Например, нельзя построить распознаватель для выяснения вопроса о существовании рациональных корней произвольного диофантова уравнения, о чем говорилось во введении. Удобно представить правила распознающей машины в форме таблицы.

Рассмотрим пример разбора c-d*e.Первая идет буква, поэтому выполняем переход из Q0 в Q1. Далее переходим в Q3. Затем (для буквы d) переходим в Q1. Затем снова в Q3. Затем в Q1 и YES.

Рассмотренная нами распознающая машина Тьюринга является частным вариантом общей машины Тьюринга, так как использует упрощенный набор правил. На самом деле этот специфический вариант машины называют автоматом. Имеются различные типы автоматов. Мы остановимся только на простейших (или регулярных) автоматах. Удобно правила регулярного автомата представлять в виде следующих формул

Qi a_k ® Qj (*)

Такое правило читается следующим образом: если автомат находится в состоянии Qi и поступает символ a_k , то автомат переходит в состояние Qj.

Для того чтобы построить таблицу разбора для регулярного автомата достаточно

Каждому правилу (*) сопоставить фрагмент таблицы следующего вида

При построении автоматов, распознающих языки, следует состояния автомата определять исходя из того, какого рода символы в этом состоянии ожидаются на входе автомата. Снова рассмотрим простой арифметический язык, но допустим, что кроме переменных языка могут встречаться и числовые константы. Пример.

a+5*c

a-b+c*10-d

a

Пусть в состоянии Q0 ожидается поступление буквы или числовой константы. В состоянии Q1 ожидается поступление знака операции. В состоянии Q2 ожидаем поступления цифры или знака операции. Отсюда получаем правила:

Q0 буква → Q1

Q1 знак_операции → Q0

Q0 цифра→ Q2

Q2 знак_операции → Q0

Q2 цифра → Q2

Вместе с тем, если ввести в язык скобки, то нельзя реализовать его распознавание с помощью регулярного автомата, поскольку нужно обеспечить распознавание парности открывающих и закрывающих скобок.

Имеет место следующий интересный результат.

Теорема. Всякий недетерминированный регулярный автомат можно реализовать с помощью эквивалентного детерминированного регулярного автомата.

Доказательство теоремы будет проведено на примере требуемой реализации.

Пусть имеется таблица недетерминированного автомата.

Недетерминизм автомата определяется наличие клетки (и подобных ей в других случаях) вида

Здесь переход из состояния Q0 под действием одного и того же символа может вести в состояние Q1 или в состояние Q2. Заменим два этих состояния на новое, например, Q3={Q1,Q2}. Теперь таблица примет такой вид:

Объясним содержимое строки Q3. Если под действием a переходим из Q0 в Q1, то под действием a из Q1 перейдем в QSTOP. Если под действием a перейдем из Q0 в Q2, то под действием a перейдем из Q2 в Q1. Отсюда получаем ячейку

Аналогичным образом получаем ячейку в столбце b.

Теперь поступаем аналогично. Заменим состояния QSTOP,Q1 на новое – Q4:

Следует просто заметить, что из QSTOP уже нет выхода. Таким образом, итоговая таблица примет следующий вид:

Рассмотрим, например, разбор слова aabb. По последней таблице попадаем в QSTOP. Варианты цепочек для соответствующего недетерминированного автомата таковы:

Q0-Q1-QSTOP

Q0-Q2-Q1-QSTOP

Q0-Q2-Q1-Q2-QSTOP